Question 9 of 12

Question 9

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. The standard insertion-sort algorithm and a list of eight asymptotic growth classes to be ordered.

Find. (a) the formal Big-O definition; (b) insertion sort's mechanism and its three complexity cases; (c) a faster comparison sort by average case; (d) the growth-rate ordering.

Approach. (a) state the standard $\exists c, n_0$ definition. (b) trace the algorithm's inner-loop shifting work in the best (already-sorted) and worst (reverse-sorted) input cases. (d) compare $\ln f(n)$ for each function as $n\to\infty$ (checked in log space at $n=2^{200}$) to rank growth rates.

1. Part (a) — definition of Big-O. $$\boxed{f(n)=O(g(n)) \iff \exists\, c>0,\ n_0\in\mathbb{N} \text{ such that } |f(n)|\le c\,|g(n)| \ \ \forall\, n\ge n_0}$$ i.e. f is eventually bounded above by a constant multiple of g, for all sufficiently large n.
2. Part (b) — how insertion sort works and its complexities. Insertion sort processes the array left to right, maintaining a sorted prefix; at step i it takes element $a_i$ and shifts it leftward past every already-sorted element greater than it, inserting it in its correct position (exactly like sorting playing cards in hand, one card at a time). Best case — already sorted: each new element is already ≥ its predecessor, so the inner "shift" loop does exactly 1 comparison and 0 shifts per element: $$\boxed{O(n)}$$ Worst case — reverse sorted: each new element $a_i$ must shift past all i previously-sorted elements, giving $\sum_{i=1}^{n}i=O(n^2)$ total comparisons/shifts: $$\boxed{O(n^2)}$$ Average case: on a random permutation, each new element is expected to shift past about half of the already-sorted prefix, so the expected total work is still $\Theta(n^2/4)=O(n^2)$ — same asymptotic class as the worst case, only a smaller constant factor: $$\boxed{O(n^2)}$$
3. Part (c) — a faster average-case algorithm. Merge sort (guaranteed $\Theta(n\log n)$ in every case) or quicksort (expected $\Theta(n\log n)$ average case) both beat insertion sort's $\Theta(n^2)$ average case: $$\boxed{\text{Merge sort (or quicksort), } O(n\log n) \text{ average}}$$
4. Part (d) — ordering by growth rate. Compare the asymptotic growth of each function: exponential $2^n$ eventually dominates every polynomial/poly-log function; among polynomials, the extra $\log n$ factor makes $n^2\log n$ dominate plain $n^2$, and $n^2$ dominates $n\sqrt n=n^{1.5}$ (ratio $\sqrt n\to\infty$); any positive power of n, including $n^{1.5}$, dominates every power of $\log n$; among the logarithmic family, $(\log n)^2$ dominates $\log n$, which dominates $\log\log n$; and any growing function eventually dominates the constant function. $$\boxed{O(2^n) \;>\; O(n^2\log n) \;>\; O(n^2) \;>\; O(n\sqrt n) \;>\; O((\log n)^2) \;>\; O(\log n) \;>\; O(\log\log n) \;>\; O(1)}$$ (listed slowest/most-time-consuming first, fastest/least-time-consuming last, as requested).