Give a brief argument that the running time of PARTITION on a subarray of size \(n\) is \(\Theta(n)\).

The primary for loop examines each element of the \(n\)-element array \(A[p..r]\) once. In the best case, no action is taken on any element but we still need to examine each one. In the worst-case, a constant time action is performed on each element and so the run time of PARTITION on an \(n\)-element array is \(\Theta(n)\).