Past exam question: 2074 Bhadra (Regular), Q9
Open in the Padhaiko appQuestion
Define big-O notation and Big- notation with their respective curves.
Solution
Big-O () Notation and Curve: iff there exist and such that for all . It defines an asymptotic upper bound.
Time
^ c * g(n)
| / ___--- f(n)
| / __/
| /_/
+-----+------------> n
n0Big-Omega () Notation and Curve: iff there exist and such that for all . It defines an asymptotic lower bound.
Time
^ f(n)
| / ___--- c * g(n)
| / __/
| /_/
+--------+---------> n
n0Answer:
Big-O ( for ) bounds growth from above (worst-case ceiling), whereas Big- ( for ) bounds growth from below (best-case floor).