# Calculating the running time of Quicksort’s PARTITION procedure

I am confused about calculating the PARTITION procedure’s running time.

PARTITION procedure is used in the Quicksort Algorithm to partition the array $$A[p…r]$$

I analyzed the PARTITION procedure provided in the book Introduction to Algorithms:

``  PARTITION(A, p, r) 1.  x= A[r] 2.  i= p-1 3.  for(j = p to r-1) 4.       if(A[j]<= x) 5.         i= i+1 6.         exchange A[i] with A[j] 7.  exchange A[i+1] with A[r] 8.  return i+1 ``

Now what I figured out that:

1. Every procedure except lines $$3-6$$ has a constant time i.e: $$\Theta(1)$$
2. For loop would execute $$r-1-p+1$$ times.

Thus the running time should be: $$\Theta(r-p)$$

While the book quotes:

The running time of PARTITION on the subarray $$A[p…r]$$ is $$\Theta(n)$$ where $$n= r-p+1$$.

Could someone please help me out in knowing how to prove the aforementioned complexity?

Thank you.