# no of times partion is called in quick sort, assuming array is always halved

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?

• (How about cheating and having some computer figure out 1+2+4…?) Apr 10, 2021 at 7:00

To count the number of partitions you just need to count the number of internal nodes in the recursion tree. Since each internal node has at least two children, the recursion tree is a full binary tree. In a full binary tree, the number of leaves and internal nodes are linearly related (see this link). So the number of internal nodes would be $$\Theta(n)$$, no matter where the partition happens. You can easily prove this using induction on the number of nodes in the tree.