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

Write a function that performs the integer mod function, Write a function t...

Write a function that performs the integer mod function. Given the previous functions you have implemented already, this one should be a piece of cake. This function will find the

Whether the infix expression has balanced parenthesis or not, Using stacks,...

Using stacks, write an algorithm to determine whether the infix expression has balanced parenthesis or not Algorithm parseparens This algorithm reads a source program and

2 way merge sort, merge sort process for an example array {38, 27, 43, 3, 9...

merge sort process for an example array {38, 27, 43, 3, 9, 82, 10}. If we take a closer look at the diagram, we can see that the array is recursively divided in two halves till the

Flowchart, conversion of centrigral to frahenhit

conversion of centrigral to frahenhit

Explain best - fit method, Best - Fit Method: - This method obtains the sma...

Best - Fit Method: - This method obtains the smallest free block whose  size is greater than or equal to get such a block by traversing the whole free list follows.

Draw a flowchart to input start time and end time of vehicle, Speed cameras...

Speed cameras read the time a vehicle passes a point (A) on road and then reads time it passes a second point (B) on the same road (points A and B are 100 metres apart). Speed of t

Design a binary search tree, Binary Search Tree usage: Write a progra...

Binary Search Tree usage: Write a program to compare the time taken for a search in a skewed tree, a balanced tree, and a random tree. Speci cally, your program should do the

Tree traversals, There are three kinds of tree traversals, namely, Postorde...

There are three kinds of tree traversals, namely, Postorder , Preorder and Inorder. Preorder traversal: Each of nodes is visited before its children are visited; first the roo

Graph & optimal scheduling, You are given an undirected graph G = (V, E) in...

You are given an undirected graph G = (V, E) in which the edge weights are highly restricted. In particular, each edge has a positive integer weight of either {1,2,...,W}, where W

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