Asymptotic Notations

For any problem, there are multiple solutions which means we can write multiple algorithms for the same problem. But how do we decide which algorithm is the best and should be implemented as proper code?

We decide that based on various factors like the time it takes to execute and get the final result, memory usage, disk i/o etc.

This is where we use Asymptotic Notations.

Big Oh (O): Upper bound - Worst Case

if f(n) <= c g(n)

for n >= n0

c > 0, n0 >= 1

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

example:

f(n) = 3n + 2

g(n) = n

is f(n) = O(g(n))?

==> 3n + 2 <= c n

==> for c = 4 , 3n + 2 <= 4n

==> n >= 2 and c = 4, f(n) = O(g(n))

Big Omega $$(\Omega)$$: Lower bound - Best case

if f(n) >= c g(n)

for n >= n0

c > 0, n0 >= 1

f(n) = $$\Omega$$(g(n))

example:

f(n) = 3n + 2

g(n) = n

is f(n) = $$\Omega$$(g(n))?

==> 3n + 2 >= c n

==> for c = 1 , 3n + 2 >= n

==> n0 >= 1 and c = 1, f(n) = $$\Omega$$(g(n))

Big Theta $$(\Theta)$$: Average case

f(n) = $$\Theta$$(g(n))

c1 g(n) <= f(n) <= c2 g(n)

c1, c2 > 0

n >= n0 where n0 >= 1