Past exam question: 2078 Poush (Back), Q3(b)
Open in the Padhaiko appQuestion
Define Omega ana Theta notation with suitable example.
Solution
Big-Omega () Notation (Asymptotic Lower Bound): A function is in if there exist positive constants and such that:
It describes the minimum growth rate (best/lower bound) of an algorithm's running time.
- Example: Let . Since for all , taking and proves .
Big-Theta () Notation (Asymptotic Tight Bound): A function is in if there exist positive constants and such that:
Equivalently, if and only if and .
- Example: For , for all :
Thus with , , , we have .
Answer:
- (Lower Bound): for all (e.g., with ).
- (Tight Bound): for all (e.g., with ).