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

+1 vote
Solve this recurrence relation: T(n) = T(n/3) + T(2n/3) + n
asked Dec 14, 2016 in Divide & Conquer by Amrinder Arora (206 points)

3 Answers

+1 vote
 
Best answer

Assume that T(n)cnlgn

So there exist c and m that let T(m)cmlgm and when n>=m, let T(n)cnlgn.

T(m)=cm/3lg(m/3)+2cm/3lg(2m/3)+m

      =cm/3(lgm-lg3)+2cm/3(lgm-lg(3/2))+m

      =cmlgm-(cm/3)lg3-(2cm/3)(lg3-lg2)+m

      =cmlgm-cmlg3+2cm/3+m

So when we let m+2cm/3-cmlg3<0  the assumption is realized

we could let c=3 m>0 then (3-3lg3)m<0 is assured

So the assumption is demonstrated and T(n)=O(nlgn).

answered May 4 by zhouce Active (276 points)
selected May 5 by Amrinder Arora
0 votes
It is O(nlgn).
answered Mar 4 by shijie Active (276 points)
Can you prove that?
0 votes

Assume T(n) ≤ cnlogn

Prove T(2)=2 
T(m) ≤ T(2m/3) + T(2m/3) +m         ( 2≤m≤n)

           ≤ 2c(2m/3)log(2m/3) + m

           = (4m/3)cm( log(2/3) + logm) + m

            = (4m/3) cmlogm + (4/3) cmlog(2/3) + m

             = (4/3) cmlogm - (4/3)cmlog(3/2) +m

             = (4/3) cmlogm – m( 4/3 log(3/2) -1)


            ≈ cmlogm

So T(m) ≤ cmlogm    T(n)≤ cnlogn

     T(n) = O(nlogn)

answered Mar 7 by sigridzy (116 points)
This doesn't look correct.  Because you say:

4/3 cm log m ~ cmlogm.

Mathematics doesn't really allow that symbol: ~

You need to prove this more clearly.
Hello Prof.Arora, what about this prove? Without enlarging the T(n/3) term to T(2n/3).
Prove T(2)=2
T(m) = T(m/3) + T(2m/3) +m         ( 2≤m≤n)

           ≤ c(m/3)log(m/3) + c(2m/3)log(2m/3) + m

           = c(m/3)log(1/3) + c(m/3)log(m) + c(2m/3)log(2/3) + c(2m/3)log(m) + m

            = cmlogm + c(m/3)log(1/3) + c(2m/3)cmlog(2/3) + m

             = cmlogm - (1/3)cmlog(3) - (2/3)cmlog(3/2) +m

             = cmlogm – m( (c/3)log(3) + (2c/3)log(3/2) -1)


            ≈ cmlogm

So T(m) ≤ cmlogm    T(n)≤ cnlogn

     T(n) = O(nlogn)
That part is much much better now.  You can still remove that ~ symbol, and simply show that the part on the right is greater than 0, so that

cm log m - z
<= cm log m

So, you just need to show that z >= 0.  That is, c/3 log 3 + 2c/3 log 3/2 > 1
The Book: Analysis and Design of Algorithms | Presentations on Slideshare | Lecture Notes, etc
...