Past exam question: 2062 Baishakh (Regular / Back), Q7(a)
Open in the Padhaiko appQuestion
Define Big 'O' notation. Compare linear logarithmic, linear and quadratic order function.
Solution
Big 'O' Notation & Order Comparison: iff there exist such that for all .
Comparing growth rates as increases:
| Order | Typical Example | ||
|---|---|---|---|
| Linear | Linear search, array sum | ||
| Linear-Logarithmic | Merge sort, Heap sort | ||
| Quadratic | Bubble, Selection, Insertion sort |
Answer:
Big-O gives an asymptotic upper bound. Growth speeds satisfy , with quadratic growing dramatically faster than linear and linear-logarithmic at large .