Asymptotic Notations

 In computer science, any problem can be solved using the programming language. And a particular problem can have multiple solutions in terms of Algorithm. To find out which one is the best algorithm for a problem, we analyse it in terms of time and space.  To define the time and space complexity of an algorithm, we use the Asymptotic notation.

Mostly three types of Asymptotic notation is widely preferred to represent the complexity of the algorithm.

Big-O mathematically represented as O

The X-axis of the above graph showing the size of the input (n) and Y axis showing the increase in  time (t). In the graph,  f(n) function showing the increase of time as input size n is increasing for a particular algorithm. Beside, the another function called cg(n) showing the worst case of f(n). Hence, in the above graph cg(n) is above the f(n).

If we bound the time complexity or f(n) of a given algorithm in terms of input n with another function called cg(n) for all the input size greater than n0 , then we can say that the f(n) is upper bound with the function g(n) with the multiple of some constant called c.
or  

f(n)<=cg(n) for all input n>=n0, and c>0 and n0>=1 . 

Then we can say that f(n) = Ocg(n), which mean f(n) is smaller than cg(n).

To understand this relation, we will see some examples:

Ex:  f(n) = 3n +2,  g(n) = n  and if we say 

               f(n)=O(g(n)),  then it should follow          

              f(n)<=cg(n) for some c>0 and n0>=1

Here

             3n+2<=cn     for some c>0 and n0>=1

To satisfy the above condition, we can assume any value of c that should greater than left size

           3n+2<=4n

simplifying the above equation, we will get the value of  n         

        2<=4n-3n

then 

          n>=2

 we can say that.....

      f(n)=3n+2, g(n)=cn

 so 

   f(n)=O(g(n))

Hence, we can say that, if g(n) bound the f(n), then it will also be bounded with g(n^2), g(n^3), g(n^4), and g(2^n). However, always try to take the tightest bound, i.e g(n).

Big-Omega mathematically represented as Ω

Similarly, the above graph shows the time complexity analysis of any algorithm in terms of Big-Omega. Suppose, for a given problem you have a algorithm. To find out the time complexity in terms of lower bound, we have define a function called f(n) and to bound it with lower bound cg(n).

i.e
f(n)>=cg(n) such that c>0, n0>=1

f(n)=3n +2 , g(n)=n
if
f(n)=Ωg(n)
than
f(n)>=cg(n)
3n+2>=cn
The above equation is true even the value of c=1 and all values of n>=1. Now, we have found out the value of c and n. Hence, we can say that f(n)=Ωg(n). This mean function f(n)=Ω(n), and the value lower than n can bound the function f(n). But, always choose the value closer to the tightest bound, i.e (n).

Big_Theta mathematically represented as Θ

     For a given problem, we have a functions c1g(n) and c2g(n) that is upper bound as well as lower bound the function f(n). Then, we can say that the time complexity of the given problem is f(n)=Θg(n). 

c

       c1g(n)<=f(n)<=c2g(n) for c1,c2>0 and for all values of n0>=1

       f(n)= 3n+2, g(n)=n

     

       Earlier, we have calculated the lower bound for this particular example, which is

      

       3n+2<=4n for all values of n0>=1, and c=4

       Similarly, we have calculated the upper bound for the this problem...

       

       3n+2>=cn for all value of n0>=1, and c=1.

      Now, we have value of c1=4 and c2=1

     

      So, we can say that, the function f(n) is upper bound and lower bound. Hence, c1g(n)<=f(n)<=c2g(n), i.e f(n)=Θg(n).

                              O                                                 Ω                                              Θ            

      (worst case analysis of algorithm)              (best case analysis)                   (Average case analysis)   

     We generally analyse of any algorithm of a given problem using the above notations. However, the 

      worst case analysis is the important analysis among all the analysis. While, the  average case analysis only performed when a problem has similar upper bound and lower bound time complexity.       

     

      Example: Searching a number in a given array of n size.

      

      Worst Case:- The element found at the last index of the array. Hence, its time complexity is O(n).

       

      Best Case:- The element is found at the first index of an array, then the time complexity Ω (n).

      Average Case:- The element is found at the middle index of an array, then the time complexity Θ(n) 

Subset relations between order-of-growth sets.