Asymptotic notation, Data Structure & Algorithms

Assignment Help:

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.


Related Discussions:- Asymptotic notation

What are the languages which support assertions, What are the languages whi...

What are the languages which support assertions Languages which support assertions often provide different levels of support. For instance, Java has an assert statement which t

In-order traversal, Write steps for algorithm for In-order Traversal Th...

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

Graph search using iterative deepening, Prove that uniform cost search and ...

Prove that uniform cost search and breadth- first search with constant steps are optimal when used with the Graph-Search algorithm (see Figure). Show a state space with varying ste

Methods, what is folding method?

what is folding method?

The space - time trade off, The best algorithm to solve a given problem is ...

The best algorithm to solve a given problem is one that requires less space in memory and takes less time to complete its execution. But in practice it is not always possible to

Multiple stacks in a single array, implement multiple stacks in an array an...

implement multiple stacks in an array and write different algorithms to perform operations on it

Function performs multiplication of two numbers, You need to write a functi...

You need to write a function that performs multiplication of two numbers in your data structure. Again, remember how you multiply numbers in base 10 and you should be fine. Multipl

Conversion of forest into tree, Conversion of Forest into Tree A binary...

Conversion of Forest into Tree A binary tree may be used to show an entire forest, since the next pointer in the root of a tree can be used to point to the next tree of the for

Abstract data types, Abstract Data Types :- A useful tool for specifying th...

Abstract Data Types :- A useful tool for specifying the logical properties of a data type is the abstract data type or ADT. The term "abstract data type" refers to the basic mathem

Representation of a sparse matrix, Let us assume a sparse matrix from stora...

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

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd