In the most even possible split, PARTITION function produces two subarrays, each of size no more than n/2. since one is of size floor(n/2) and one of size ceil(n/2)-1.
The recurrence for the running time will be,
$$ T(n) = 2T(n/2) + \Theta(n) $$
where we tolerate the sloppiness from ignoring the floor and ceiling and from subtracting 1. By case 2 of the master theorem, this recurrence will have the solution $$ T(n) = \Theta(n \log n) $$ My Implementation is as follows:
QUICKSORT(A, p, r) if p < r q = PARTITION(A, p, r) QUICKSORT(A, p, q-1) QUICKSORT(A, q+1, r)
PARTITION(A, p, r) x = A[r] i = p - 1 for j = p to (r - 1) if A[j] <= x i = i + 1 exchange A[i] with A[j] exchange A[i+1] with A[r] return i + 1
Assuming that the array is always divided into 2 equal halves, how many times is the partition algorithm will be called?