Past exam question: 2078 Baishakh (Back), Q5
Open in the Padhaiko appQuestion
Explain about Big-Oh notation with its significance and limitation.
Solution
Definition of Big-Oh () Notation: A function is if there exist positive constants and such that:
Big-Oh provides an asymptotic upper bound on the growth rate of an algorithm's resource usage (usually worst-case time).
Significance and Limitations of Big-Oh:
- Significance:
- Guarantees worst-case performance will not grow faster than .
- Enables hardware-independent comparison of algorithms as input size .
- Simplifies analysis by discarding constant factors and lower-order terms.
- Limitations:
- Ignores Constant Factors: An algorithm with constant can be slower than an algorithm for small practical inputs .
- Asymptotic Only: Does not capture behavior for small .
- Only an Upper Bound: Saying is technically true for linear time , so it may be loose unless paired with or .
- Ignores Cache/Hardware Effects: Locality of reference and disk I/O constants are hidden.
Answer:
Big-Oh () bounds worst-case growth from above ( for ). Its significance is hardware-independent worst-case comparison at scale; its limitations are hiding constant factors, small- behavior, hardware cache effects, and potentially giving loose bounds.