Past exam question: 2079 Ashwin (Back), Q10
Open in the Padhaiko appDefine Big-Oh and Theta notation with suitable example.
Solution
Big-Oh Notation () — Asymptotic Upper Bound: Mathematical Definition: Let and be functions mapping positive integers to non-negative real numbers. We say:
if and only if there exist positive constants and such that:
Interpretation: Big-Oh provides an asymptotic upper bound on the growth rate of . It guarantees that as the input size grows arbitrarily large, the running time of the algorithm will never exceed (characterizing worst-case performance).
Example for Big-Oh Notation: Let . Prove that .
For all :
Thus, we have:
By choosing constant multiplier and threshold , the formal definition is strictly satisfied for all . Hence:
Theta Notation () — Asymptotic Tight Bound: Mathematical Definition: Let and be non-negative functions. We say:
if and only if there exist positive constants , , and an integer such that:
Interpretation: Theta notation sandwiches from both above and below within constant factor multiples of . This means grows at the identical asymptotic rate as ( and simultaneously).
Example for Theta Notation: Using the same function . Prove that .
- Lower Bound (): For all :
- Upper Bound (): For all :
Combining both inequalities for all :
With , , and , the definition of holds. Therefore:
- Big-Oh Notation (): Formal upper bound: for . Example: with .
- Theta Notation (): Formal tight bound (sandwiched from above and below): for . Example: with .