Past exam question: 2075 Baisakh (Back), Q9
Open in the Padhaiko appQuestion
Describe the importance of growth function in algorithm. Discuss about theta function, Big-Oh function and Omega function.
Solution
Importance of Growth Function: A growth function models how an algorithm's execution time or memory scales with input size . It matters because:
- It reveals which algorithm remains practical as grows large (e.g., vs. for ).
- It ignores machine-specific constants so algorithms can be compared independently of CPU speed or compiler.
- It guides selection of data structures (e.g., hash table vs. array) before coding.
Big-Oh (), Big-Omega (), and Theta () Functions:
- Big-Oh ( — Upper Bound): for all (worst-case ceiling).
- Big-Omega ( — Lower Bound): for all (best-case floor).
- Theta ( — Tight Bound): for all ( grows at the exact same rate as ).
Answer:
A growth function predicts scalability with input size independent of hardware. gives an asymptotic upper bound, gives an asymptotic lower bound, and gives a tight two-sided bound.