Solve the recurrence $T(n) = T(\lfloor n/2 \rfloor)+ T(\lfloor n/3 \rfloor) + \lfloor n \log_2 n\rfloor$.

Question

$T(0) = T(1) = T(2) = 1$. For $n \geq 3, T(n) = T(\lfloor n/2 \rfloor)+ T(\lfloor n/3 \rfloor) + \lfloor n \log_2 n\rfloor$. Express the above recursion in $O(n)$ notation. I know how to solve recurrence in the form of $T(n) = aT(n/b) + f(n)$. However, I have no idea how to solve the above recurrence. Is there any trick to do this.

Answer 1

We can guess the answer by iteratively refining our guess. (All logarithms here are binary.)

Start with $T(n) \in Θ(n)$. Right-hand side is too big; we should increase $T$ because $1 > \frac12+\frac13$.

Try $T(n) \in Θ(n\log(n))$. Well so we want roughly $k n \log(n) = k (\frac12+\frac13) n \log(n) + n \log(n)$. From this we immediately can guess $k$. Now this may not be right since we ignored the floors, but it turns out that we can prove this guess correct. To do so we use any positive constants $a,b$ such that $a < k < b$ and prove by induction that $T(n) \in [a,b] n \log(n) + [-c,c]$ for every natural $n$, where $c$ is some constant to be determined (from whatever the proof requires), where here of course we do not ignore the floors.