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
#include #include int sumFact(int numb); int calculateFactorial(int digit); main() { int numb, sumfact; do{ printf ("Enter a number 1 to 9999\n"); scanf("%

In the last subsection, we have implemented a stack by using an array. While a stack is implemented by using arrays, it suffers from the basic restriction of an array - i.e., its s

Q1. Define a sparse matrix. Explain different types of sparse matrices? Evaluate the method to calculate address of any element a jk of a matrix stored in memory. Q2. A linear

What do you mean by complexity of an algorithm? The complexity of an algorithm M is the function f(n) which gives the running time and/or storage space need of the algorithm i

reverse the order of elements on a stack S using two additional stacks using one additional stack

State the range of operation of ADT Operations of the Range of T ADT includes following, where a, b ∈ T and r and s are values of Range of T: a...b-returns a range value (an

A driver takes shortest possible route to attain destination. The problem which we will discuss here is similar to this type of finding shortest route in any specific graph. The gr

The  total  of  time  needed  by  an algorithm to run to its completion is termed as time complexity. The asymptotic running time of an algorithm is given in terms of functions. Th

Program segment for deletion of any element from the queue delete() { int delvalue = 0; if (front == NULL) printf("Queue Empty"); { delvalue = front->value;

Binary tree creation struct NODE { struct NODE *left; int value; struct NODE *right; }; create_tree( struct NODE *curr, struct NODE *new ) { if(new->val