0

I am trying to solve the following recurrence $T(n) = T(n/3)+T(2n/3) + O(n)$ by either substitution or recursion tree method. I have seen examples online that solve this recursion for $$\Omega$$ lower bound but not tight upper bound. How can this be solved for tight upper bound?

My tree:

1st level : $T(n)$

2nd level : $T(n/3)$ and $T(2n/3)$ node

3rd level : $T(n/9),\,T(2n/9),\,T(2n/9),\,T(4n/9)$

4th level : $T(1)$

Apologies for my tree, I'm not sure how to draw the tree on here.

Substitution method: I know that you guess and apply mathematical induction Guess: $T(n) \leq cn\text{lg}(n)$

HallaSurvivor
  • 38,115
  • 4
  • 46
  • 87
newtoMobileDev
  • 3
  • I'm newer to this, so I guess I don't know it as well as I thought I did – newtoMobileDev May 20 '21 at 18:06
  • The substitution $T(n)=An^{c_\text{crit}}\ln^kn$ will probably help more than the recursion tree method. You should find $c_\text{crit}=k=1$. – J.G. May 20 '21 at 18:10
  • I have only seen this be solved by recursion tree. Would you be able to show me how it is solved by substitution method? I was trying to do it by master method but I haven't seen an example with two terms. – newtoMobileDev May 20 '21 at 18:14

1 Answers1

1

Welcome to MSE!

Hint:

Notice each level of your tree sums of to $n$ much work:

  • your top level has size $n$
  • your second level has size $n/3 + 2n/3 = n$
  • your third level has size $n/9 + 2n/9 + 2n/9 + 4n/9 = n$
  • can you show (by induction, say) that this always works?

The issue, of course, is that you're traversing this tree at different rates. So the $n/3$ branches are going to die off faster than the $2n/3$ branches because you're descending the tree more quickly. This makes the analysis look really hard, because near the bottom of the tree, we won't sum to $n$. Some of the terms we need to get to a sum of $n$ will have died already.

The trick is to notice that we don't care. We want a big $O$ bound. So let's find out what the maximal length could possibly be, and then assume everything survives that long. This will give us the upper bound we want.

It's clear that the "rightmost" path, that is, the one that always scales by $2/3$ is going to take the longest time getting to $1$. Can you see how many levels this branch of the tree will have? If $\ell(n)$ is the number of levels in this branch (which is an upper bound for the number of levels of every branch), we'll have:

$$ T(n) \leq \sum_{l \leq \ell(n)} O(n) = O \left ( n \cdot \ell(n) \right ) $$

I hope this helps ^_^

HallaSurvivor
  • 38,115
  • 4
  • 46
  • 87
  • I know that the longest path is log 3/2n but I am having troubles showing it by induction. – newtoMobileDev May 20 '21 at 18:29
  • You don't need to show it by induction! What does the logarithm do? If exponentiation is repeated multiplication, logarithmiation is repeated division. Since we're repeatedly dividing by $3/2$, we need $\log_{3/2}(n)$ many steps to do this. – HallaSurvivor May 20 '21 at 18:48
  • Oh ok. I was taught that after using a recursion tree we had to use induction to prove the initial guess holds for any n. – newtoMobileDev May 20 '21 at 18:52