Asymptotic Notation

Asymptotic Notation

Asymptotic notation is a shorthand way to represent the time complexity. Asymptotic notation is used to measure the efficiency of algorithm and this efficiency is depends on amount of required time, storage and other sources ehich are required to execute the program.

Asymptotic analysis are refers the mathematical boundation used to describe the run time performance of an algorithm. Using the asymptotic analysis,

 

It include the best case, average case, and worst case of an algorithm.

Worst case

The input for which the algorithm takes a so much time is called worst case

Average case

Average case takes average time for the execution of program.

Best case

Best case defines the input for which the algorithm takes the lowest time

There are three types of asymptotic notations:

• • • Big-O notation
    • Omega notation
    • Theta notation

1. Big-O Notation (O-notation)

Big O notation is denoted by ‘O’.It is a method of representing the upper bound of algorithm’s running time.Using big o  notation we cangive longest amount of time taken by the algorithm to complete. It is set of functions that grow slower than or at the same rate as expression.It indicates the maximum required by an algorithm for all input values.

 

 

For example, for a function f(n)

Ο(f(n)) = { 

g(n) : there exists c > 0 and n0
 such that f(n) ≤ c*g(n) for all n > n0. 
}

2. Omega Notation (Ω-notation)

Omega notation is denoted by Ω. This notation is used to represent the lower boundary of algorithm’s running time.Using omega notation we can denote shortest amount of time taken by algorithm.

A function F(n) is said to be in Ω (g(n)) if F(n) is bounded beloe by some positive constant multiple of g(n) such that

F(n) >= c*g(n)     For all n>=n₀

 

 

For example, for a function f(n)

Ω(f(n)) ≥ { 
 g(n) : exists c > 0 and n0
 such that g(n) ≤ c*f(n) for all n > n0
 }

3. Theta Notation (Θ-notation)

The theta notation is denotes by Θ. By this method the running time is between upper bound and lower bound. It consist of all the function that lie in both O and Omega expression. It indicates the average bound of an algorithm .

 

 

For example, for a function f(n)

θ(f(n)) = {
g(n) only if g(n) = Ο(f(n)) and
g(n) = Ω(f(n)) for all n > n0
}

 

Read more, Data structure and Types