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
Do you have a library solution for this problem?

Draw trace table and determine output from the following flowchart using following data: Number = 45, -2, 20.5

Area Subdivision Method In this method, the viewport is examined for clear decisions on the polygons situated in it, in regard to their overlap and visibility to the viewer. Fo

In this assignment, you are invited to design and implement a software system for catalogue sale. A catalogue is organised in a tree structure. Each node of the catalogue tree repr

A binary tree is a tree data structures in which each node have at most two child nodes, generally distinguished as "right" and "left". Nodes with children are called parent nodes,

A database is a collection of data organized in a manner that facilitates updation, retrieval and management of the data. Searching an unindexed database having n keys will have a

Q. What do you understand by the tree traversal? Write down the procedure for traversing a binary tree in preorder and execute it on the following tree.    Ans: Th

Q. Explain w hat are the stacks? How can we use the stacks  to check whether an expression is correctly parentheses or not. For example (()) is well formed but (() or )()( is not w

What values are automatically assigned to those array elements which are not explicitly initialized? Garbage values are automatically assigned to those array elements that

Prim's algorithm employs the concept of sets. Rather than processing the graph by sorted order of edges, this algorithm processes the edges within the graph randomly by building up