The theta-notation, Data Structure & Algorithms

Assignment Help:

This notation bounds a function to in constant factors. We say f(n) = Θ(g(n)) if there presents positive constants n0, c1 and c2 such that to the right of n0 the value of f(n) always lies between c1g(n) and c2g(n), both inclusive. The given Figure gives an idea about function f(n) and g(n) where f(n) = Θ(g(n)) . We will say that the function g(n) is asymptotically tight bound for f(n).

1562_The Theta-Notation.png

Figure: Plot of  f(n) = Θ(g(n))

 

For instance, let us show that the function f(n) =  (1/3) n2   - 4n = Θ(n2).

Now, we must determined three positive constants, c 1, c 2 and no as

c1n2 ≤1/3 n2 - 4n c2 n2 for all n no

c1 ≤ 1/3- 4/n  ≤ c2

By choosing no = 1 and c2 ≥ 1/3 the right hand inequality holds true.

 

Likewise, by choosing no = 13, c1  ≤  1/39, the right hand inequality holds true. Thus, for c1 = 1/39 , c2 = 1/3 and no  ≥ 13, it follows that 1/3 n2 - 4n = Θ (n2).

Surely, there are other alternative for c1, c2 and no. Now we might illustrates that the function f(n) = 6n3    ≠  Θ (n2).

In order to prove this, let us suppose that c3 and no exist such that 6n3   ≤ c3n2  for n ≥ no, But this fails for adequately large n. Therefore 6n3    ≠  Θ (n2).


Related Discussions:- The theta-notation

Link list, algorithm for multiplication of two sparse matrices using link l...

algorithm for multiplication of two sparse matrices using link list

Polynomials - represented by using arrays, /* the program accepts two polyn...

/* the program accepts two polynomials as a input & prints the resultant polynomial because of the addition of input polynomials*/ #include void main() { int poly1[6][

Simulation of queues, Simulation is the process of making an abstract model...

Simulation is the process of making an abstract model of a real world situation in order to be aware of the effect of modifications and alterations and the effect of introducing nu

Traversing a graph, two standards ways of traversing a graph in data struc...

two standards ways of traversing a graph in data structure

Progrrame, how to write a code for for a company , for calculate the salary...

how to write a code for for a company , for calculate the salary pay

Depth-First Traversal, With the help of a program and a numerical example e...

With the help of a program and a numerical example explain the Depth First Traversal of a tree.

Areas of use - sequential files, Sequential files are most frequently utili...

Sequential files are most frequently utilized in commercial batch oriented data processing where there is the concept of a master file on which details are inserted periodically. F

Algorithm, what algorithms can i use for the above title in my project desi...

what algorithms can i use for the above title in my project desing and implmentation of road transport booking system

Algorithm to sort a given list by quick sort method, Q. Write down an algor...

Q. Write down an algorithm to sort a given list by making use of Quick sort method. Describe the behaviour of Quick sort when input given to us is already sorted.

Algorithm, Example of worse case of time

Example of worse case of time

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd