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

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!

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

• Comments are not for extended discussion; this conversation has been moved to chat. – D.W. Nov 7 '19 at 19:49

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.

• Comments are not for extended discussion; this conversation has been moved to chat. – D.W. Nov 7 '19 at 19:49