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.