Recurrence relation : T(n) = T(n/3) + 2 T(2n/3) + n

Question

Solve the recurrence relation:T(n)=T(n/3)+2T(2n/3)+n.

Answer 1

T(n) = T(n/3) + 2T(2n/3) + n

First of all, we are able to guess that this is going to be something like n^c, since this is at least as much as R(n) = 2R(2n/3) + n.  To analyze R(n), we see that: a = 2, b = 1.5, f(n) = n, which can be solved using MT, and gives a simple n^(log_1.5(2)), that is, n^(log 2/log 1.5), which is ~ n^1.71

Suppose T(n) <= k n^c

We want to choose any k, smallest c, such that following is true.

k n ^ c / 3^c + 2 k 2^c n^c / 3^c + n <= k n^c

As a sanity check, c >= 1.  Based on previous analysis, we will see that c >= 1.71

• n <= n^c (k – k/3^c – 2 k 2^c / 3^c)
• 1 <= n ^ (c-1)   k [1 – 1/3^c – 2 2^c / 3^c]                // Our sanity check is reinforced here, c >= 1

Say c = 1, this becomes negative: 1 – 1/3 – 4/3  (Negative).  So, this is not good.  We want the term to be non-negative.

That is, we want that 1 - 1/3^c - 2 2^c /3^c >= 0

• 1/3^c + 2 2^c / 3^c <= 1
• 1 + 2 2^c <= 3^c
• 1 <= 3^c – 2 2^c

c >= 2

Comments

Dear Prof, I'm confused. According to your method, we can find c >= 2. However, If you suppose T(n) = O(n^2), T(n) <= a n^2, then T(n) =T(n/3)+2T(2n/3)+n <= a n^2 + n, which is not <= a n^2. What's wrong here?

---

Try by assuming: T(n) <= a n^2 - 2n.  Then you get that T(n) = T(n/3) + 2T(2n/3) + n <= an^2 - 2n/3 - 2.2.(2n/3) + n
<= an^2 - n

---

I guess there is typo. The last expression should be an^2 - 2n, right? Well, this assumption does not seem intuitive to be guessed at the first place. Does it mean that we ought to change our assumption during the process of proving?

---

I got it, we can try at the first place assumptions as: T(n) <= a n^k - b f(n), if O(f(n)) = O(n^k), which seems more generally applicable, right?

---

Right, sometimes that assumption may not appear intuitive, but it is a common pattern, and once you have seen it, you will apply it at other places.  The basic idea is that if you make a stronger claim, you are able to use the stronger claim in the Induction Hypothesis portion of the proof by PMI.

---

Thank you so much.

---

But...Why T(n) is at least as much as R(n)? I know how to com up with the answer by using MT but cannot understand the relationship between T(n) and R(n). Thx!

---

Hello Professor! Why do we do the Master Theorem on R(n) at first? And according to the discussion of this answer, if we come up with different assumption of T(n), we reach different forms of T(n).  For example, in your answer you proved that T(n) <=kn^c when c>2; in the discussion, you said that T(n) <= an^2-n. Are these two all acceptable? Does this mean that there exists many forms of T(n) to one recursive expression of T(n)?

Answer 2

I wrote a simple python script to simulate it, and  here is the code; hope it's right -_-.

def myFunction(n: int):
    if n == 0:
        return 1
    else:
        return myFunction(int(n / 3)) + 2 * myFunction(int(2.0 * n / 3)) + n

And I calculated several sequences of n and plotted the input and output. 

Comments

Hello! Could you please specify what do the yellow line and the blue line stand for? This answer is detailed to help me understand the question :-)