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 linked list can be of the following types:-  Linear linked list or one way list Doubly linked list or two way list. Circular linked list Header linked list

a) Find the shortest paths from r to all other nodes in the digraph G=(V,E) shown below using the Bellman-Ford algorithm (as taught in class). Please show your work, and draw the f

#question. merging 4 sorted files containing 50,10,25,15 records will take time?

The following DNA sequences are extracted from promoter region of genes which are co-regulated by the same transcription factor (TF). The nucleotide segments capitalized in the giv

what do you understand by structured programming?explain with eg. top down and bottem up programming technique

What is A Container Taxonomy It's useful to place containers in a taxonomy to help understand their relationships to one another and as a basis for implementation using a class

The smallest element of an array's index is called its Lower bound.

Explain in brief about the Container An entity which holds finitely many other entities. Just as containers such as boxes, baskets, bags, pails, cans, drawers, and so for

A graph is a mathematical structure giving of a set of vertexes (v1, v2, v3) and a group of edges (e1, e2, e3). An edge is a set of vertexes. The two vertexes are named the edge en

Beauty Salon is a system to be designed to manage the booking and the payment of a single beauty parlour. Beauty Therapists: A beauty parlour has a number of staff members mo