7.1-3

7.1-3 Give a brief argument that the running time of PARTITION on a subarray of size n is $\theta(n)$

In the worst i and j will be incremented n -1 times.Hence the upper bound is $O(n)$. In the best and average case i may not be incremented n-1 times but there still will be n-1 comparisons hence the best case running time is $\Omega(n)$. Hence the running time of the algorithm is $\theta(n)$