# How to compute the complexity of $T(n) = 2T(\frac{n}{2}) +O(n\log n)$

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

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

• In my case, it is $O(n\log n)$. It is different from $\Theta(n\log n)$. Dec 6, 2023 at 20:39
• sr, it should be $O(n\log n)$ ? Dec 6, 2023 at 21:04
• 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)$). Dec 6, 2023 at 21:09
• Many thanks to you Dec 8, 2023 at 11:43

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

• 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. Dec 6, 2023 at 21:26
• 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). Dec 6, 2023 at 21:30
• 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}). Dec 6, 2023 at 21:32
• Repeat this for few step and you will see the pattern. Dec 6, 2023 at 21:32