Consider an algorithm with the following recursion $$ T(n) \leq T(n/3) + T(2n/3) + \mathcal O(n)$$ for its running time. I understand that $T(n) = \mathcal O(n \log n)$ by drawing the recursion tree and seeing that every level takes time $n$, and that the depth of the tree is $\log_{3/2} n$. But, why is this upper bound tight?


1 Answer 1


What you write is tight in the sense that if you have no additional information than the recurrence you wrote, then you cannot hope to prove any better asymptotic upper bound.

To see this consider: $$ T'(n) = T'(n/3) + T'(2n/3 ) + n, $$ and notice that this could be the case in your recurrence.

The associate recursion tree will have at least $\Omega(\log_3 n)$ full levels, and, since $\frac{n}{3} + \frac{2n}{3}= n$, the overall time spent on each of these levels is $n$. This shows that $T'(n) = \Omega(n \log n)$.

Notice however that there are choices of $T$ for which $O(n \log n)$ is not asymptotically tight. For example: $$ T''(n) = T''(n/3) + T''(2n/3) + 1, $$ which has solution $T''(n)=\Theta(n)$, or even just $T(n) = c$ for any positive constant $c$.


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.