Asymptotic Analysis example.

 

Let us say that the time complexity for solving this problem is 

f(x)<= g(x) {upper bound}

this is big O notation . Whenever we get <= sign , it is always big o notation . the worst case and it means the maximum time that a program takes.

* Omega Notation best case.

* Theta Notation Average case.

This means that this problem is bound to be solved b/w n^2 . It is a strict timing . It should always be the case.

So if a problem is getting solved by 3 different ways n<n^2< 2^n , then we cannot write it with theta notation. If the program every time is being solved by order of n or n^2 , then only we can write it by theta notation.