Solving $T(n) = T(n/2) + T (n/3) + n $ with recurrence tree

Question

I am trying to solve the following recurrence relation: $$T(n) = T(n/2) + T (n/3) + n $$ $$T(1) = Θ(1) $$

I guess that the time complexity is $T(n)=Θ(n)$ since $\frac{n}{2} + \frac{n}{3} < n$

I am trying to prove it using a recurrence tree.

The tree is not balanced. Particularly, the longest path from the root to a leaf is the leftmost one with a length of $\log_2n$ when the shortest path is the rightmost one with a length of $\log_3n$.

We get that at each level,except the first one, the cost is $< n$. In more detail,the first level has a cost of $n$. The nodes on the second level add to a $\frac{5}{6}\cdot n$ cost, the third level has a cost equal to $\left (\frac{5}{6} \right )^2\cdot n$ and so on...

So, untill the height of $\log_3n$ we have a cost of $$n\sum_{i=0}^{\log_3n-1}\left (\frac{5}{6} \right )^i = n\cdot \frac{\left (\frac{5}{6}\right)^{\log_3n}-1}{\left (\frac{5}{6}\right)-1}$$

So, the result above seems to be a lower bound for my function $T(n)$

Is my approach correct? If yes, then how do I go on in order to prove that the time complexity is $T(n)=Θ(n)$.Thanks in advance!

Answer 1

On the one hand, clearly $T(n) \geq n$ (see detailed proof below). On the other hand, let us find prove by induction that $T(n) \leq Cn$, for large enough $C$. The base case trivially holds for $C \geq T(1)$. For the inductive step, we have $$ T(n) = T(n/2) + T(n/3) + n \leq C\cdot (n/2) + C\cdot (n/3) + n = [\tfrac{5}{6}C+1]n. $$ (We're cheating here a bit since $n$ isn't necessarily a multiple of 6.) If $C \geq 6$, then $\tfrac{5}{6}C+1 \leq C$, and so we can conclude that $T(n) \leq Cn$, thus completing the inductive step. In total, if we take $C = \max(T(1),6)$ then the proof goes through, hence $$ n \leq T(n) \leq \max(T(1),6) n. $$ This implies that $T(n) = \Theta(n)$.

---

Finally, let us prove that $T(n) \geq n$. We first prove that $T(n) \geq 0$. The proof by induction. The base case clearly holds, and the inductive step is a consequence of $$ T(n) = T(n/2) + T(n/3) + n \geq 0 + 0 + 0, $$ using the inductive hypothesis twice. Finally, $$ T(n) = T(n/2) + T(n/3) + n \geq 0 + 0 + n = n. $$

Answer 2

Defining base cases:

$T(0) = 0;$

$T(1) = 0;$

I got: $$ T(n) = n \; (\sum_{r = 0}^{log_3 \; {n}} [ \binom{log_3 \; {n}}{r} \; log_2 \; [{(\frac{2}{3})^r \; n}] \; + \; \sum_{r = 0}^{log_2 \; {n}} [ \binom{log_2 \; {n}}{r} \; log_2 \; [{(\frac{3}{2})^r \; n}]) $$

$$ $$

You can do the approximation & the bounding yourselves.

Sorta took me longer to format this properly than solve this.