Tree method or PMI?

Question

For some recurrence we can not use MT, we often guess an answer and prove it through PMI. However, I think that the answer is not close.

For example:

http://notexponential.com/293/recurrence-relation-t-n-t-n-3-2-t-2n-3-n

The PMI answer here is T(n) = T(n/3) + 2T(2n/3)+n = O(n²).

In my solution, I assume that the tree could fully extend.

The 1st level is Θ(n);

The 2nd level is Θ((5/3)*n);

The 3rd level is Θ((5/3)²*n);

....

The nth level is Θ((5/3)^n-1*n).

And the height of the left tree is log₃n, because the height of right tree is less than the value. Here I just assume they have the same height. Then the bottom level is n*T(1) since the tree has n leaves.

Thus,

T(n) = n*T(1) + n + (5/3)*n + (5/3)²*n + ... + (5/3)^log₃n-1*n = n + n*((1 - (5/3)^log₃n-1)/(1 - (5/3))) 

= n + (3/2)*n*(5/3)^log₃n-1 ~ n + (3/2)*n*(5/3)^log₃n = n + (3/2)*n*n^log₃(5/3) ~ n + n^1.5.

Actually, the tree can not fully extend, T(n) < n + n^1.5, T(n) = O(n^1.5).

PMI answer is O(n²) while tree method answer is O(n^1.5). Which one is the right answer?

Answer 1

Each method has its own advantages and disadvantages, but the analysis given in the question is not correct.  The time complexity of this recurrence is not O(n^1.5).

[The analysis presented above should be checked again.  For example, consider this statement: 

Then the bottom level is n*T(1) since the tree has n leaves.

I am not sure this statement is supported by analysis.

Comments

Thank you professor. However, **I assumed that the tree fully extends and its height is log_3 n**, so the bottom level h is 3^h = 3^(log_3 n) = n^(log_3 3) = n. The Instruction to Algorithms (Instruction to Algorithms, 3rd Edition, Section 4.4, P90) used this method which I used here.

---

Hi, Taoran. Actually, the longest path of the tree should be log3/2(n). So you should not assumed that its height is log3(n).

---

Yes, you are right and I find my mistake. Thank you.