Asymptotic notation, Data Structure & Algorithms

Asymptotic notation

Let us describe a few functions in terms of above asymptotic notation.

Example: f(n) = 3n3 + 2n2 + 4n + 3

= 3n3 + 2n2 + O (n), as 4n + 3 is of O (n)

= 3n3+ O (n2), as 2n2 + O (n)   is O (n2)

= O (n3)

Example: f(n) = n² + 3n + 4 is O(n²), since n² + 3n + 4 < 2n² for all n > 10.

Through definition of big-O, 3n + 4 is also O(n²), too, although as a convention, we employ the tighter bound to the function, i.e., O(n).

Here are some rules regarding big-O notation:

1. f(n) = O(f(n)) for any function f. In other terms, every function is bounded by itself.

2. aknk + ak-1 n k-1 + • • • + a1n + a0 = O(nk) for every k ≥ 0 & for all a0, a1, . . . , ak ∈ R.

In other terms, every polynomial of degree k may be bounded through the function nk. Smaller order terms can be avoided in big-O notation.

3. Basis of Logarithm can be avoided in big-O notation that means logan = O(logb n) for any bases a, b. Generally we write O(log n) to specify a logarithm n to any base.

4. Any logarithmic function may be bounded through a polynomial that means. logb n = O(nc) for any b (base of logarithm) & any positive exponent c > 0.

5. Any polynomial function may be limited by an exponential function i.e. nk = O (bn.).

6.Any exponential function may be limited by the factorial function. For instance, an = O(n!) for any base a.

Posted Date: 4/4/2013 5:46:24 AM | Location : United States







Related Discussions:- Asymptotic notation, Assignment Help, Ask Question on Asymptotic notation, Get Answer, Expert's Help, Asymptotic notation Discussions

Write discussion on Asymptotic notation
Your posts are moderated
Related Questions
Gouraud Shading The faceted appearance of a Lambert shaded model is due to each polygon having only a single colour. To avoid this effect, it is necessary to vary the colour ac

If a node having two children is deleted from a binary tree, it is replaced by?? Inorder successor

algorithm to search a node in linked list

In the last section, we discussed regarding shortest path algorithm that starts with a single source and determines shortest path to all vertices in the graph. In this section, we

The pre-order and post order traversal of a Binary Tree generates the same output. The tree can have maximum One node

1. Define the following terms in a rule-based expert system? a) Knowledge base b) Inference engine 2. What is a fuzzy rule? Explain the difference between classical and fuzzy

The searching method are applicable to a number of places in current's world, may it be Internet, search engines, text pattern matching, on line enquiry, finding a record from data

Q. Write down an algorithm to convert an infix expression into the postfix expression.     Ans. Algo rithm to convert infix expression to post fix expression is given as

Q. Write down a non recursive algorithm to traverse a binary tree in order.                    Ans: N on - recursive algorithm to traverse a binary tree in inorder is as