How many recursive calls are made when quicksort is size n

Question

How many recursive calls are necessary when quickSort sorts an array of size n if you use median-of-three pivot selection?

I thought the answer is n times because isnt this the best case?

Answer 1

The median-of-three heuristic does not guarantee the best case at all. In fact, it does not even avoid the worst case behavior, still $O(N^2)$ comparisons.

But whatever the case and the choice strategy for the pivot, processing must continue until the initial array has been partitioned in chunks of constant size, and this always takes $O(N)$ recursive calls.

Also note that when the "smallest first" strategy is used, the recursion depth cannot exceed $O(Log(N))$, whereas without care, it can remains a very bad $O(N)$.