I'm currently studying computational complexity and I've stumbled upon this question:
Calculate the complexity of the following algorithm by using
recurrence tree: $$T(n) = T(n/2) + T(n/3) + T(n/5) + n$$
I have no idea how to calculate this with a recurrence tree, since it is divided in three different parts. I've tried to draw the recurrence tree and was not able to find any pattern for the nodes.
Also, I've tried to generalize it into a single denominator, but without success.
Anyone can help me? Thanks!
Best Answer
Welcome to MSE!
The trick for solving problems like this (at least roughly) is to look at how things branch, and bound the number of layers in our tree.
Eventually, some of these branches will die out (and end at leaves), but as long as all of our branches still exist at level $k$, we know exactly how much gets contributed:
$$\left ( \frac{1}{2} + \frac{1}{3} + \frac{1}{5} \right )^k n$$
(do you see why?)
But, I hear you saying. What do we do once we get far enough down the tree that branches do start dying? The answer is "stop caring". We can get upper and lower bounds on our recursion by working with the longest and shortest branches (respectively). After all, if we just stop summing when the first branch dies, we'll get a lower bound that's easy to compute. Conversely, if we keep summing up until the last branch dies, pretending that our levels are still full, we'll get an upper bound that's easy to compute!
The longest branch in this tree has length $\log_2(n)$, and the shortest has length $\log_5(n)$ (again, do you see why?) So we know the true solution to our recurrence lives somewhere in the range
$$ n \sum_{k = 0}^{\log_5 n} \left ( \frac{1}{2} + \frac{1}{3} + \frac{1}{5} \right )^k \leq T(n) \leq n \sum_{k = 0}^{\log_2 n} \left ( \frac{1}{2} + \frac{1}{3} + \frac{1}{5} \right )^k $$
But using our formula for a (partial) geometric series and condensing our sum of fractions to $\frac{31}{30}$, we find (ignoring constants)
$$ \Omega \left ( n^{1 + \log_5 \frac{31}{30}} \right ) \leq T(n) \leq O \left ( n^{1 + \log_2 \frac{31}{30}} \right ) $$
In other words, $n^{1.02} \lesssim T(n) \lesssim n^{1.04}$.
If you want tighter control than this, you'll need heavier-hitting machinery. For instance, you can use the Akra-Bazzi Theorem to show that $T = \Theta(n^p)$ where $p \approx 1.0328$ is such that
$$ \frac{1}{2^p} + \frac{1}{3^p} + \frac{1}{5^p} = 1 $$
I hope this helps ^_^