The theta-notation, Data Structure & Algorithms

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).

Posted Date: 4/4/2013 5:42:48 AM | Location : United States







Related Discussions:- The theta-notation, Assignment Help, Ask Question on The theta-notation, Get Answer, Expert's Help, The theta-notation Discussions

Write discussion on The theta-notation
Your posts are moderated
Related Questions
A significant aspect of Abstract Data Types is that they explain the properties of a data structure without specifying the details of its implementation. The properties might be im

for (i = 0; i sequence of statements } Here, the loop executes n times. Thus, the sequence of statements also executes n times. Since we suppose the time complexity of th

Example: Assume the following of code: x = 4y + 3 z = z + 1 p = 1 As we have been seen, x, y, z and p are all scalar variables & the running time is constant irrespective

Q. Write down the algorithm for binary search. Which are the conditions under which sequential search of a list is preferred over the binary search?

Define a B-Tree Justas AVL trees are balanced binary search trees, B-trees are balanced M-way search trees. A B-Tree of order M is either the empty tree or it is an M-way searc

Find a minimum cost spanning arborescence rooted at r for the digraph shown below, using the final algorithm shown in class. Please show your work, and also give a final diagram wh



the deference between insertion,selection and bubble sort

Q.1 Write procedures/ Algorithm to insert and delete an element in to array. Q.2. Write an algorithm for binary search. What are the conditions under which sequential search of