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
Question 1. How can you find out the end of a String? Write an algorithm to find out the substring of a string. 2. Explain the insertion and deletion operation of linked lis

Assume you are in the insurance business. Find two examples of Type 2 slowly changing dimensions in that business. As an analyst on the project, write the specifications for applyi

C compiler does not verify the bounds of arrays. It is your job to do the essential work for checking boundaries wherever required. One of the most common arrays is a string tha

Let us assume a sparse matrix from storage view point. Assume that the entire sparse matrix is stored. Then, a significant amount of memory that stores the matrix consists of zeroe

Q. Take an array A[20, 10] of your own. Suppose 4 words per memory cell and the base address of array A is 100. Find the address of A[11, 5] supposed row major storage.

Each data record contains a fixed place in a relative file. Each record ought to have associated with it in integer key value which will help identify this slot. Therefore, this ke

RENDERING, SHADING AND COLOURING By introducing hidden line removal we have already taken one step away from wire-frame drawings towards being able to realistically model and d

Algo rithm to Insert a Node p at the End of a Linked List is explained below Step1:   [check for space] If new1= NULL output "OVERFLOW" And exit Step2:   [Allocate fr

RGB Model The RGB model is based on the assumption that any desired shade of colour can be obtained by mixing the correct amounts of red, green, and blue light. The exact hues

Definition of Algorithm Algorithm must have the following five characteristic features: 1.      Input 2.      Output 3.      Definiteness 4.      Effectiveness 5