Loading....
Coupon Accepted Successfully!

 

Asymptotic Notations

These notations are used to describe the Running time of an algorithm, in terms of functions, whose domains are the set of natural numbers, N = {1, 2, ……}. Such notations are convenient for describing the worst case running time function. T(n) (problem size input size). The complexity function can be also be used to compare two algorithms P and Q that perform the same task. The basic Asymptotic Notations are:

  1. O(Big-”Oh”) Notation. [Maximum number of steps to solve a problem, (upper bound)]
  2. Ω (Big-”Omega”) Notation [Minimum number of steps to solve a problem, (lower bound)]
  3. θ (Theta) Notation [Average number of steps to solve a problem, (used to express both upper and lower bound of a given )f(n)).

The Notation O (BIG ‘Oh’)

Big ‘Oh’ Notation is used to express an asymptotic upper bound (maximum steps) for a given function f(n). Let f(n) and g(n) are two positive functions, each from the set of natural numbers (domain) to the positive real numbers.


We say that the function f(n) = O (g(n)) [read as “f of n is big “Oh” of g of n”], if there exist two positive constants C and N0 such that

493.png 


The intuition behind O-notation is shown in figure-1

498.png 

Fig. 1


For all values of n to the right of n0, the value of f(n) is always lies on or below Cg(n).

The Notation Ω (BIG ‘Omega’)

 

O-Notation provides as asymptotic upper bound for a function; Ω-Notation provides as asymptotic upper bound for a function; Ω-Notation, provides an asymptotic lower-bound for a given function.


We say that the function 503.png [read as “f of n is big “Omega” of g of n”], if and only if there exist two positive constants C and n0 such that

508.png 
 

513.png 

Fig. 2


Note that for all values of f(n) always lies on or above g(n).

The Notation θ (Theta)

  

Θ-Notation provides simultaneous both asymptotic lower bound and asymptotic upper bound for a given function.

Let f(n) and g(n) are two positive functions, each from the set of natural numbers (domain) to the positive real numbers. In some cases, we have 518.png and 523.png then 528.png.


We say that the function 533.png [read as “f of n is Theta” of g of n”], if and only if there exist three positive constants C1, C2 and n0 such that

538.png for all 543.png ...(i)


(Note that this inequality (1) represents two conditions to be satisfied simultaneously viz 548.png and 553.png 

clearly this implies if f(n) = O (g (n)) and f = Ω (g(n)) then f(n) = Θ (g(n)).


The following figure-1 shows the intuition behind the Θ-Notation.

 

558.png 

Fig. 3


Note that for all values of n to the right of the n0 the value of f(n) lies at or above C1g(n) and at or below C2.g(n).

Hence inequality (1) simultaneously satisfied for C1 = 1,

C2 = 2 and 563.png.

Hence f(n) = Θ (g(n)).

Minimum Cost Spanning Trees (Prim’s Algorithm)

 

The algorithm is outlined below. It finds the set of edges T of a minimum cost spanning tree.

  1. T  {}; X {1}; Y  V – {1}
  2. while Y  {}
  3. Let (x, y) be of minimum weight such that 568.png and 573.png.
  4. 578.png 
  5. 583.png 
  6. 588.png 
  7. end while





Test Your Skills Now!
Take a Quiz now
Reviewer Name