# Modified Quicksort*

given array of size n, and a function called FindPivot which returns the median with a time complexity of O(n^(1.1)). what is the worst case time complexity of quicksort using the given func to find pivot?

the answer given by the teacher is theta(n^(1.1)) I thought it should be theta(n^1.1logn) please explain

– user16034
Commented Feb 22, 2023 at 20:31

Since the function returns the median, the time complexity of (this version of) Quicksort is described by the recurrence equation: $$T(n) = 2 T(n/2) + O(n^{1.1}).$$

By the Master theorem, this has solution $$T(n) = O(n^{1.1})$$.

It is not possible to conclude that $$T(n) = \Theta(n^{1.1})$$ from the given information since, e.g., FindPivot might run in time $$\Theta(n)$$ (recall that $$\Theta(n) \subset O(n^{1.1})$$), in which case the resulting complexity would be $$\Theta(n \log n)$$.

If we further assume that FindPivot runs in time $$\Theta(n^{1.1}$$) then the recurrence equation becomes $$T(n) = 2 T(n/2) + \Theta(n^{1.1})$$, which has solution $$T(n) = \Theta(n^{1.1})$$.

• thank you! that helped Commented Feb 22, 2023 at 7:19

Intuitively, many small components of equal size in a recursion formula often result in a log n factor, which is smaller than any power.

In your case, your recursion has 2 * T(n/2) ≈ T(n) * 2 / 2^1.1 = T(n) / 2 ^1.1. Now the smaller components in your recursion shrink like a geometric series. You are not adding up items of equal size, so there is no factor log n.

Note that if we just compare n^1.1 and n ln n, the first one is larger from n = 5,000,000,000,000,000 and then quickly gets a lot faster.