Quicksort time complexity

The pseudocode of quicksort1:

function quicksort(arr) {
  if (arr.length < 2) return arr;
  const [pivot, ...rest] = arr;
  const [less, greater] = partition(rest, pivot);
  return [...quicksort(less), pivot, ...quicksort(greater)];
}
js

Let the time taken by quicksort() be T(n)T(n) where nn = arr.length.

T(n)=c⋅n+∑k=0n−1(P(K=k)⋅(T(k)+T(n−k−1)))=c⋅n+1n∑k=0n−1(T(k)+T(n−k−1))=c⋅n+2n∑k=0n−1T(k)\begin{aligned} T(n) &= c\cdot n + \sum_{k = 0}^{n - 1}\left(P(K = k)\cdot (T(k) + T(n-k-1))\right)\\ &= c\cdot n + \frac{1}{n}\sum_{k = 0}^{n - 1}\left(T(k) + T(n-k-1)\right)\\ &= c\cdot n + \frac{2}{n}\sum_{k = 0}^{n - 1}T(k)\\ \end{aligned}

Substitute n=n−1n = n - 1.

T(n−1)=c⋅(n−1)+2n−1∑k=0n−2T(k)n−1n⋅T(n−1)=c⋅(n−1)2n+2n∑k=0n−2T(k)T(n)−n−1n⋅T(n−1)=c⋅2n−1n+2n∑k=0n−1T(k)−2n∑k=0n−2T(k)\begin{aligned} T(n - 1) &= c\cdot (n - 1) + \frac{2}{n - 1}\sum_{k = 0}^{n - 2}T(k)\\ \frac{n - 1}{n}\cdot T(n - 1) &= c\cdot\frac{(n - 1)^2}{n} + \frac{2}{n}\sum_{k = 0}^{n - 2}T(k)\\ T(n) - \frac{n - 1}{n}\cdot T(n - 1) &= c\cdot \frac{2n - 1}{n} + \frac{2}{n}\sum_{k = 0}^{n - 1}T(k) - \frac{2}{n}\sum_{k = 0}^{n - 2}T(k)\\ \end{aligned}

Now we solve for the upper bound.

T(n)=n−1n⋅T(n−1)+2n⋅T(n−1)+c⋅2n−1n≤n+1n⋅(T(n−1)+2c)=n+1n⋅T(n−1)+c⋅2n+2n≤n+1n⋅nn−1⋅(T(n−2)+2c)+c⋅2n+2n=n+1n−1⋅T(n−2)+c⋅(2n+2n−1+2n+2n)≤…≤(n+1)⋅T(0)+c⋅(2n+2)∑i=1n1i→n→∞(n+1)⋅O(1)+c⋅(2n+2)ln⁡n=O(nln⁡n)\begin{aligned} T(n) &= \frac{n - 1}{n}\cdot T(n - 1) + \frac{2}{n}\cdot T(n - 1) + c\cdot \frac{2n - 1}{n}\\ &\leq \frac{n + 1}{n}\cdot (T(n - 1) + 2c)\\ &= \frac{n + 1}{n}\cdot T(n - 1) + c\cdot\frac{2n + 2}{n}\\ &\leq \frac{n + 1}{n}\cdot \frac{n}{n - 1}\cdot (T(n - 2) + 2c) + c\cdot\frac{2n + 2}{n}\\ &= \frac{n + 1}{n - 1}\cdot T(n - 2) + c\cdot\left(\frac{2n + 2}{n - 1} + \frac{2n + 2}{n}\right)\\ &\leq \dots\\ &\leq (n + 1)\cdot T(0) + c\cdot (2n + 2)\sum_{i = 1}^n\frac{1}{i}\\ &\xrightarrow{n\to\infty} (n + 1)\cdot \mathcal{O}(1) + c\cdot (2n + 2)\ln n\\ &= \boxed{\mathcal{O}(n\ln n)} \end{aligned}

Footnotes

  1. It's pseudocode because you don't implement quicksort like this. Real quicksort is in-place because copying like ...rest is actually O(n)\mathcal{O}(n). Still, this is a correct (and O(nln⁡n)\mathcal{O}(n\ln n)) implementation. ↩