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?