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:

- Every procedure except lines $ 3-6$ has a constant time i.e: $ \Theta(1)$
- 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.