solving the recurrance by the method of substitution

Question

While learning the algorithms and referring to CLRS, I came across a problem

T(n) = T(n-a) + T(a) + cn ; a >= 1 and c > 0
it is Big-theta(n^2), can be easily proved by recursion tree method

I can solve it by the method of recursion tree.

While discussing with friends at my lab, a friend declared out of nowhere that this problem can never be solved by the method of substitution.

I tried solving it myself, but cannot find any pattern as such.

Moreover, my expanding in the first step seems somewhat wrong to me:

T(n) = T(n-2a + T(a) + c(n-1)) + T(a) + cn
T(n) = T(n-3a + 2T(a) + c(n-1)(n-2)) + T(a) + cn

And this seems to be going nowhere..

Can you solve it by method of substitution? What is your 'guess'?

Answer 1

Your first line of expansion is not good, but the second is logical (look at it closely, you have not done the same thing twice regarding the brackets).

Here is how you could do it:

T(n) = T(n-a) + T(a) + cn
T(n) = T(n-2a) + T(a) + c(n-a) + (T(a) + cn)
     = T(n-2a) + 2T(a) + c(2n-a)
     = T(n-3a) + T(a) + c(n-2a) + (2T(a) + c(2n-a))
     = T(n-3a) + 3T(a) + c(3n - 3a)
...
    = T(n-ka) + kT(a) + ck(n - (k-1)a/2)  // The last part come from n+(n-a)+...+(n-(k-1)a) = k(n - (k-1)a/2)

To generalize, you can see that, at step j, decomposing T(n-ja) will give you T(n-(j+1)a), one new T(a), and a c(n-ja). Then,

Sum(c(n-ja), j=0..k-1)=c*(k*n - a*Sum(j), j=0..k-1))
                      = c(kn-a*(k-1)k/2)

Which gives you the result.

Take k=n/a, you get:

T(n) = T(0) + nT(a)/a + c(n/a)(n-(n/a-1)a/2)

which gives roughly

T(n) ~ nT(a)/a + c n^2 /(2a)

which is Theta(n^2) since c>0.