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 quicksort algorithm description task, and 8 named growth-rate functions to be ranked.

Find. A description of quicksort with its average-case complexity, and the correct slowest-to-fastest ordering of the 8 functions.

Approach. Describe quicksort's partition-then-recurse structure and quote its standard average-case bound; rank the growth functions by evaluating (or bounding) each at large $n$ and comparing pairwise, grouping polynomial, quasi-polynomial, and (sub)exponential families.

1. 9a) How quicksort works. Quicksort is a divide-and-conquer sort: pick a pivot element from the array; partition the remaining elements into two sub-arrays — those less than the pivot and those greater than or equal to it — placing the pivot between them in its final sorted position; then recursively apply the same procedure to each sub-array; the base case is an array of size 0 or 1, which is trivially sorted. No merge step is needed because partitioning already leaves every element on the correct side of the pivot.
2. 9a) Average-case complexity. With a reasonably balanced pivot choice (e.g. random pivot, or median-of-three), each partition splits the array into two roughly equal halves on average, giving the recurrence $T(n)=2T(n/2)+O(n)$, which by the Master theorem solves to $$\boxed{T_{\text{avg}}(n)=O(n\log n)}$$ (worst case, from a consistently unbalanced split such as an already-sorted array with a naive first-element pivot, is $O(n^2)$).
3. 9b) Rank by comparing logarithms. Since $\log$ is increasing, $f$ grows faster than $g$ exactly when $\log f-\log g\to\infty$. Taking $\ln$ of each function: $\ln(\log n)=\ln\ln n$, $\ln\sqrt n=\tfrac12\ln n$, $\ln(n\log n)=\ln n+\ln\ln n$, $\ln(n^3\log n)=3\ln n+\ln\ln n$, $\ln(n^4)=4\ln n$, $\ln\big(n^{\log n}\big)=\log n\cdot\ln n=\Theta\big((\ln n)^2\big)$, $\ln\big(2^{\sqrt n}\big)=\sqrt n\,\ln 2$, $\ln(n^n)=n\ln n$. The first five are ordered by their $\ln n$ coefficients ($\ln\ln n\prec\tfrac12\ln n\prec\ln n+\ln\ln n\prec 3\ln n+\ln\ln n\prec4\ln n$; note $n^4/(n^3\log n)=n/\log n\to\infty$). Next, $(\ln n)^2$ outgrows every constant multiple of $\ln n$, so $n^{\log n}$ outgrows every polynomial. $\sqrt n\ln2$ outgrows $(\ln n)^2$ because any positive power of $n$ outgrows any power of $\ln n$, so $2^{\sqrt n}$ outgrows $n^{\log n}$. Finally $n\ln n\gg\sqrt n$, so $n^n$ is the largest of all. Caution: the order of $2^{\sqrt n}$ and $n^{\log n}$ only settles for large $n$. With $\log=\log_2$, $n^{\log_2 n}=2^{(\log_2 n)^2}$, and $(\log_2 n)^2\lt\sqrt n$ holds for every $n\gt2^{16}=65{,}536$ (at $n=2^{16}$ both equal 256). A spot-check at $n=1000$ gives the wrong order ($2^{\sqrt{1000}}\approx 3\times10^{9}$ is far below $1000^{\log_2 1000}\approx10^{30}$). Big-O compares limiting behaviour, so the ranking is taken as $n\to\infty$.