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
Two-dimensional array is shown in memory in following two ways:  1.  Row major representation: To achieve this linear representation, the first row of the array is stored in th

what do we use asymptotic notation in study of algorithm?Describe various asymptotic notation and give their significance.

Adjacency list representation An Adjacency list representation of Graph G = {V, E} contains an array of adjacency lists mentioned by adj of V list. For each of the vertex u?V,

write aprogram for random -search to implement if a[i]=x;then terminate other wise continue the search by picking new randon inex into a

There are three typical ways of recursively traversing a binary tree. In each of these, the left sub-trees & right sub-trees are visited recursively and the distinguishing feature

AVL trees are applied into the given situations: There are few insertion & deletion operations Short search time is required Input data is sorted or nearly sorted

What is String Carrier set of the String ADT is the set of all finite sequences of characters from some alphabet, including empty sequence (the empty string). Operations on s


what are the disadvantages of sparse matrix?

1. Define the following terms in a rule-based expert system? a) Knowledge base b) Inference engine 2. What is a fuzzy rule? Explain the difference between classical and fuzzy