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 are grounded header linked lists?

Efficiency of Linear Search How much number of comparisons is there in this search in searching for a particular element? The number of comparisons based upon where the reco

According to this, key value is divided by any fitting number, generally a prime number, and the division of remainder is utilized as the address for the record. The choice of s

Determine the greatest common divisor (GCD) of two integers, m & n. The algorithm for GCD might be defined as follows: While m is greater than zero: If n is greater than m, s

Let us assume a sparse matrix from storage view point. Assume that the entire sparse matrix is stored. Then, a significant amount of memory that stores the matrix consists of zeroe

Here is a diagram showing similarities between documents; this is an actual set of physics lab assignments from a large university. Each node (square) in the graph is a doc

State about the pre- and post conditions Programmers can easily document other pre- and post conditions and class invariants, though, and insert code to check most value preco

Write steps for algorithm for In-order Traversal This process when implemented iteratively also needs a stack and a Boolean to prevent the execution from traversing any portion

Step 1: Choose a vertex in the graph and make it the source vertex & mark it visited. Step 2: Determine a vertex which is adjacent to the source vertex and begun a new search if

Construct a B+ tree for the following keys, starting with an empty tree.  Each node in the tree can hold a maximum of 2 entries (i.e., order d = 1). Start with an empty root nod