CLRS Solutions | Exercise 7.1-3

Give a brief argument that the running time of $\textsc{Partition}$ on a subarray of size $n$ is $\Theta(n)$.

Intuitivelye, the $\textsc{Partition}$ procedure performs a constant amount of work for each element in the subarray, making its running time linear.

More formally, let’s examine the procedure’s structure:

$$\textsc{Partition}(A, p, r)$$$$\begin{aligned} 1& \quad x\,=\,A[r] \\ 2& \quad i\,=\,p\,-\,1 \\ 3& \quad \textbf{for }\,j\,=\,p\textbf{ to }\,r\,-\,1 \\ 4& \quad \qquad \textbf{if }\,A[j]\,\leq\,x \\ 5& \quad \qquad \qquad i\,=\,i\,+\,1 \\ 6& \quad \qquad \qquad \text{exchange}\,A[i]\,\text{with}\,A[j] \\ 7& \quad \text{exchange}\,A[i + 1]\,\text{with}\,A[r] \\ 8& \quad \textbf{return }\,i\,+\,1 \\ \end{aligned}$$

Lines 1–2 perform constant-time initialization, setting the pivot $x$ and index $i$. The for loop in lines 3–6 is the heart of the algorithm. It executes exactly $r - p$ times (once for each element from $p$ to $r - 1$). Since the subarray has $n = r - p + 1$ elements, the loop runs $n - 1$ times.

Inside the loop, each iteration does constant work: one comparison (line 4), and possibly an increment (line 5) and a swap (line 6). Swapping two array elements takes $\Theta(1)$ time regardless of whether it actually occurs. After the loop, lines 7–8 perform one final swap and a return, both taking constant time.

We can express the total running time as:

\[\begin{align*} T(n) &= \Theta(1) + (n-1) \cdot \Theta(1) + \Theta(1) \\ &= \Theta(n) \end{align*}\]

The key observation is that the for loop dominates the running time, and it performs a constant number of operations per element. No matter what values are in the array, we always examine each element exactly once, making the running time $\Theta(n)$ in all cases (best, worst, and average).