Question

Write a note on Asymptotic notation.

Answer 1

Asymptotic Notations:
Asymptotic Notations are languages that use meaningful statements about time and space complexity.

(I) Big O
Big O is often used to describe the worst–case of an algorithm.

(II) Big Ω
Big Omega is the reverse Big O, if Bi O is used to describe the upper bound (worst–case) of an asymptotic function, Big Omega is used to describe the lower bound (best-case).

(III) Big Θ
When an algorithm has complexity with lower bound = upper bound, say that an algorithm has a complexity O (n log n) and Ω (n log n), it actually has the complexity Θ (n log n), which means the running time of that algorithm always falls in n log n in the best – case and worst – case.