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
What is the best-case number of comparisons performed by mergesort on an input sequence of 2 k distinct numbers?

Example: (Double left rotation while a new node is added into the AVL tree (RL rotation)) Figure: Double left rotation when a new node is inserted into the AVL tree A

A small shop sells 280 different items. Every item is identified by a 3 - digit code. All items which start with a zero (0) are cards, all items which start with a one (1) are swee

By changing the NULL lines in a binary tree to the special links called threads, it is possible to execute traversal, insertion and deletion without using either a stack or recursi

Determine the Components of Illumination The light reaching the eye when looking at a surface has clearly come from a source (or sources) of illumination and bounced off the su

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

Write a C++ program with header and source les to store street addresses using the Doubly Linked List ADT. Modify the Node class from Lab Assignment 3 so that it becomes a node in

Program: Creation of Doubly Linked List OUTPUT Input the values of the element -1111 to come out : 1 Input the values of the element -1111 to come out : 2 Inpu

Declaring a two dimensional array   A two dimensional array is declared same to the way we declare a one-dimensional array except that we state the number of elements in both di