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

Question

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

Answer 1

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

Comments

Assuming c log(n), once again, seems like magic numbers to me. Why would someone automagically assume n log n and not n here?

---

Can we solve this recurrence relation like this T(n/3) + T(2n/3) = T (n)
So T(n) + n = n logn if we use the master theorem.

---

No, I don't think that way is correct.  Because, if you get T(n) = T(n) + n, that doesn't make much sense.   If you are trying to get an intuition into the guess, then it is better to assume that:

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

is similar to

S(n) = 3 S(n/3) + n
Then, using Master Theorem, we can derive that S(n) = n log n.

Then, we can "guess" that the same answer *MIGHT* be true for T(n), and then we can prove it using the method described above.

---

@Basil - Sure, it is a magic number.  The thought process behind it is:

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

is *similar* to

S(n) = 3 S(n/3) + n
Then, using Master Theorem, we can derive that S(n) = n log n.

Then, we can "guess" that the same answer *MIGHT* be true for T(n), and then we can prove it using the method described above.

Answer 2

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)

Comments

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

Answer 3

Came across an alternative approach to solve this question,

The Akra-Bazzi theorem provides a method for solving certain types of recurrence relations that don't fit directly into the standard forms covered by the master theorem. The Akra-Bazzi theorem is applicable to recurrence relations of the form:

T(n) = g(n) + Σ_{i=1to k} ai *T(bi *n + h_i(n)),

where ai and  bi are constants, and hi(n) are functions satisfying certain conditions. In this case, k = 2, a1 = a2 = 1, b1 = 1/3, b2 = 2/3, and h1(n) = h2(n) = 0.

First we check conditions ,as we can see all conditions satisfied from above.

next we check Regularity Condition:

 Σ_{i=1to k} |ai/ bi^{-1}|^p = 1.

Σ_{i=1to k} |ai/ bi^{-1}|^p = (1/(1/3)^p) + (1/(2/3)^p) = 3^p + (3/2)^p ~= 1 for all p>1

The Akra-Bazzi theorem states that if the conditions are satisfied, the solution T(n) is equivalent to
      Θ (n^p (1 + ∫_{1to n} g(u) / u^{1+p} du)).

Here g(n) = n and p = |ai / bi| *(1 + hi'(n) / n^{1 + hi(n)}) = 3^{-1} + (2/3)^{-1} = 1. [Since, h1(n) = h2(n) = 0]. By substituting the values in above equation stated,  we get

 Θ (n (1 + ∫_{1to n} u / u2 du)) = Θ (n (1 + ∫_{1to n}  1/u du)) = Θ (n (1 + log n)) = Θ (n + n log n)

= Θ (n log n)