1
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – D.W. Nov 7 '19 at 19:49
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – D.W. Nov 7 '19 at 19:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.