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
Preorder traversal of a binary tree struct NODE { struct NODE *left; int value;     /* can take any data type */ struct NODE *right; };   preorder(struct N

You are supposed to do the following: Write a parallel implementation of the raytracer using pthreads. Measure and compare the execution times for (i) the sequential ver

In-order Traversal  This process when executed iteratively also needs a stack and a Boolean to prevent the implementation from traversing any portion of a tree twice. The gener

how to learn about time complexity of a particular algorithm

A binary tree is a special tree where each non-leaf node can have atmost two child nodes. Most important types of trees which are used to model yes/no, on/off, higher/lower, i.e.,

Program gives the program segment by using arrays for the insertion of an element to a queue into the multiqueue. Program: Program segment for the insertion of any element to t

As part of an experiment, a school measured heights (in metres) of all its 500 students. Write an algorithm, using a flowchart that inputs the heights of all 500 students and ou

Objectives The purpose of this project is to give you significant exposure to Binary Search Trees (BST), tree traversals, and recursive code. Background An arbitrary BST i

how to creat atm project by using linked list?

1) preorder, postorder and inorder 2) The main feature of a Binary Search Tree is that all of the elements whose values is less than the root reside into the nodes of left subtr