-1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Can you justify your answer ? $\endgroup$
    – user16034
    Commented Feb 22, 2023 at 20:31

2 Answers 2

0
$\begingroup$

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})$.

$\endgroup$
1
  • $\begingroup$ thank you! that helped $\endgroup$
    – WalaWizon
    Commented Feb 22, 2023 at 7:19
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.