Asymptotic Notations And Time Complexity analysis

Time Complexity And Asymptotic Notations

lTime Complexity : The time complexity of an algorithm is the amount of time taken by operating system To run or execute the program.

Ex: we have an expression where we have to perform various operations-

                 1. 2ײ + 3× + 5 -(2׳+3)(×+1)

                    Total addition operators = 4

                    Total subtraction operators=1

                           Total  multiplicative operator=1

                           show the Time complexity

                           T(n)=[P1(add)+P2(sub)+P3(mul)]

lSpace Complexity : space complexity of an algorithm is the amount of space needed to keep the input and the attributes of the program ,the compilation space. Sometimes an auxiliary memory space is used if needed.

Space complexity =  (Auxiliary space + Input size)

a = Worst case  

b = Average case

c = best case

n = number of steps

P = problem size

Time complexity of an algorithm is depends upon the number of steps having by and algorithm.

Types of algorithm analysis:

l Posteriori analysis : Under the shade of this analysis a programmer first implement the code then judge it's time complexity. It is considered to be the best tool for performance measurement. 

l Apriori analysis: This analysis is contrary of a posteriory analysis, here the programmer first analyze the complexity of the code before executing it. 

Ø Dominance Relation :

a =O(log n)

b =O(n½)

c =O(n)

d=O(n log n)

e=O(n²)

f =O(n³)

g=O(2^n)

h=O(n!)

i=O(n^n)

                        

Asymptotic Notations-

Five types of notation are there -

l Big-O notation : Big O Notation is used to indicate the upper bound or we can say tight bound point of the function. expression of this notation is-

      O(g(n)) = { f(n): there exist positive constants c and n0 such that f(n) ≤ cg(n) for all n ≥ n0 }

l Omega notation (Ω) : This notation is used to indicate the lower bound point of a function. Its expression is shown as-              

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

lTheta notation(Θ) : Theta notation is used to indicate the average bound point of a function. expression of this notation is-

Θ(g(n)) = { f(n): there exist positive constants c1, c2 and n0 such that 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ n0

                                               or

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

Hence we can say that above function also satisfies theta notation.

Let's see another ex-

Two additional notations are as follow:

l  Little-o notation(o) : As we know that the Big-O notation is used to indicate upper bound of a function. But it's more interesting testing to know that the little 'o' notation is used to indicate the upper bound that can't be tight.   

In mathematical relation,we can express it as:    f(n) = o(g(n)) means      lim  f(n)/g(n) = 0

                  n→∞

l   Little omega(ω) : Let f(n) and g(n) be functions that map positive integers to positive real numbers. We say that f(n) is ω(g(n)) if for any real constant c > 0, there exists an integer constant n0 ≥ 1 such that f(n) > c * g(n) ≥ 0 for every integer n ≥ n0.

In mathematical relation,we can express it as:     f(n) ∈ ω(g(n)) then

                 lim  f(n)/g(n) = ∞

                    n→∞