The theta-notation, Data Structure & Algorithms

Assignment Help:

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


Related Discussions:- The theta-notation

Algorithms, Data array A has data series from 1,000,000 to 1 with step size...

Data array A has data series from 1,000,000 to 1 with step size 1, which is in perfect decreasing order. Data array B has data series from 1 to 1,000,000, which is in random order.

Structures for complete undirected graphs, Q. Draw  the structures of compl...

Q. Draw  the structures of complete  undirected  graphs  on  one,  two,  three,  four  and  five vertices also prove that the number of edges in an n vertex complete graph is n(n-1

Define the carrier set of the symbol abstract data type, Define the Carrier...

Define the Carrier set of the Symbol ADT Carrier set of the Symbol ADT is the set of all finite sequences of characters over Unicode characters set (Unicode is a standard char

Process of post-order traversal, Post-order Traversal This can be done ...

Post-order Traversal This can be done both iteratively and recursively. The iterative solution would need a change of the in-order traversal algorithm.

Deletion from a red-black tree, Deletion in a RBT uses two main processes, ...

Deletion in a RBT uses two main processes, namely, Procedure 1: This is utilized to delete an element in a given Red-Black Tree. It involves the method of deletion utilized in

Write the algorithm to find input and output value, This algorithm inputs 5...

This algorithm inputs 5 values and outputs how many input numbers were positive and how many were negative. Data to be used: N = 1, -5, 2, -8, -7

Search on a heap file, Consider the file " search_2013 ". This is a text fi...

Consider the file " search_2013 ". This is a text file containingsearch key values; each entry is a particular ID (in the schema given above). You are tosimulate searching over a h

What are the objectives of visual realism applications, What are the Object...

What are the Objectives of visual realism applications After studying this unit, you should be able to know specific needs of realism, add realism to pictures by el

Define a b-tree, Define a B-Tree Justas AVL trees are balanced binary s...

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

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd