Past exam question: 2066 Jestha (Back), Q8(a)
Open in the Padhaiko appQuestion
Define Big 'O' notation and describe the rules to determine the order of common functions. Compare linear, quadratic, logarithmic, linear logarithmic order functions.
Solution
Big 'O' Notation & Rules for Determining Order: iff there exist such that for all . Rules for Order Determination:
- Drop Multiplicative Constants: .
- Keep Only Highest-Order Term (Sum Rule): .
- Nested Loops Multiply (Product Rule): A loop of inside gives .
- Logarithm Base Invariance: for any constant bases .
Comparison of Common Growth Orders (Slowest to Fastest Growth):
| Order | Name | Growth at | Typical Algorithm Example |
|---|---|---|---|
| Logarithmic | Binary search, AVL lookup | ||
| Linear | Sequential search, array traversal | ||
| Linear-Logarithmic | Merge sort, Heap sort, Quick sort (avg) | ||
| Quadratic | Bubble, Insertion, Selection sort |
Answer:
Big-O bounds worst-case growth from above using constant-dropping, dominant-term sum, and loop-product rules. Growth order ranks: .