Give a brief argument that the running time of
PARTITIONon a subarray of size $n$ is $\Theta(n)$
There is a for statement whose body executes $r - 1 - p = \Theta(n)$ times. In the worst case every time the body of the if is executed, but it takes constant time and so does the code outside of the loop. Thus the running time is $\Theta(n)$.