0 votes

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(n2).

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)2*n);

....

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

And the height of the left tree is log3n, 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)2*n + ... + (5/3)log3n-1*n = n + n*((1 - (5/3)log3n-1)/(1 - (5/3))) 

= n + (3/2)*n*(5/3)log3n-1 ~ n + (3/2)*n*(5/3)log3n = n + (3/2)*n*nlog3(5/3) ~ n + n1.5.

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

PMI answer is O(n2) while tree method answer is O(n1.5). Which one is the right answer?

in Divide & Conquer by AlgoStar (440 points)

1 Answer

+1 vote
 
Best answer

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(n1.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.

by AlgoMeister (1.6k points)
selected by
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.
The Book: Analysis and Design of Algorithms | Presentations on Slideshare | Lecture Notes, etc
...