0
$\begingroup$

I'm trying to solve the recurrent $$T(n) = 2T\left(\frac{n}{2} \right) +O(n\log n)$$

I thought about Master's theorem but unfortunately, my recurrent doesn't belong to any cases enter image description here

Could you please help me with solving my difficulties? Thank you a lot for your help.

$\endgroup$

2 Answers 2

1
$\begingroup$

It does not make sense to talk about the complexity of a recurrence equation. Algorithms have complexities (sometimes expressed via recurrence equations). Recurrences have solutions.

Anyway, your recurrence is covered by the second case of the master theorem formulation you posted. More precisely, if $T(n) = a T(n/b) + f(n)$ where $f(n) = \Theta(n^{\log_b a} \log^k n)$ for some $k > -1$, then $T$ has solution $T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$.

In your specific case $a=b=2$ and $k=1$, therefore the solution is $T(n)=O(n \log^2 n)$.

$\endgroup$
4
  • $\begingroup$ In my case, it is $O(n\log n)$. It is different from $\Theta(n\log n)$. $\endgroup$
    – Pipnap
    Dec 6, 2023 at 20:39
  • $\begingroup$ sr, it should be $O(n\log n)$ ? $\endgroup$
    – Pipnap
    Dec 6, 2023 at 21:04
  • $\begingroup$ Yes, there was a typo in my previous comment, $\log n$ should have been $n \log n$. To restate it correctly: The solution to $T(n)=2T(n/2)+Θ(n \log n)$ is an (asymptotic) upper bound to the solution of $T(n)=2T(n/2)+O(n \log n)$. Therefore you have $T(n)=O(n \log^2 n)$ as per the answer. Moreover, this solution is tight in the sense that you cannot prove $T(n)=o(n \log^2 n)$ without further assumptions on what the function $f(n)$ hidden by the $O(n \log n)$ notation is (since it might be the case that $f(n)=Θ(n \log n) \subset O(n \log n)$). $\endgroup$
    – Steven
    Dec 6, 2023 at 21:09
  • $\begingroup$ Many thanks to you $\endgroup$
    – Pipnap
    Dec 8, 2023 at 11:43
1
$\begingroup$

Consider $n = 2^k$ and then expand the recurrence.

$\displaystyle T(n) = 2T(\frac{n}{2}) + O(nlog(n)) = O(k2^k + 2(k-1)2^{k-1} + 2^2T(2^{k-2})) = O(\sum^{k}_{i = 0} 2^{i} (k-i) 2^{k-i}) = O(2^k \sum^{k}_{i=0} (k-i)) = O(k^2 2^k) = O(nlog^2(n))$

$\endgroup$
4
  • $\begingroup$ Hello, thank you for your reply. Could you please explain more? I am just a beginner. I don't understand the second and the third equality. Many thanks. $\endgroup$
    – Pipnap
    Dec 6, 2023 at 21:26
  • $\begingroup$ Ok just replace $n = 2^k$. $nlog(n)$ becomes $k2^k$. $2T(n/2)$ becomes $2T(2^{k-1})$. Now expand 2T(2^{k-1}) similar to T(n) i.e. T(2^k). $\endgroup$ Dec 6, 2023 at 21:30
  • $\begingroup$ If you replace n = 2^k your equation becomes T(2^k) = 2T(2^{k-1}) + O(k2^k). Similarly T(2^{k-1}) = O((k-1)2^{k-1}) + 2T(2^{k-2}). $\endgroup$ Dec 6, 2023 at 21:32
  • $\begingroup$ Repeat this for few step and you will see the pattern. $\endgroup$ Dec 6, 2023 at 21:32

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.