Take the 2-minute tour ×

I am given this recurrence relation:

T (n) = T (n − a) + T (a) + cn

C > 0 , a >= 1 ..

my problem is with T (a) , I don't understand how you can "recurs" a constant??

Like, if am trying to build a recurrence tree, I would go by doing this:

T (n) =>  cn            =>         cn
         /  \                    /    \
      T(a)  T(n - a)           ca      c*(n-a)
                             /    \     /     \
                            ??    ??  T(n-2a)  T(a)

You see what I mean? What does T(a) represent??

Any resource will be much appreciated. Thanks.

OR, think of it iteratively:

T (n) = T (n -2a) + T (a) + ????
share|improve this question
I saw this similar question ... It seems to be also called "iteration method" ... stackoverflow.com/questions/2053459/… –  Mazyod Mar 25 '11 at 4:19
add comment

1 Answer

up vote 0 down vote accepted

So you have:


What is T(n-a)? Simply take n-a as your input:

T(n-a) = T((n-a)-a) + T(a) + c(n-a)

Now what is T(a)? Similarly, take a as an input:

T(a) = T(a-a) + T(a) + ca

Combining them, you obtain:

T(n) = ( T((n-a)-a) + T(a) + c(n-a) )+ ( T(a-a) + T(a) + ca ) + cn
     = T(n-2a) + T(a) + c(n-a) + T(0) + T(a) + ca + cn
     = T(n-2a) + 2T(a) + T(0) + c((n-a) + a + n)

Now depending on your base case, T(0) probably is some constant. Hope that helps.

share|improve this answer
When do you stop replacing T (a) ??? –  Mazyod Mar 25 '11 at 6:46
like, if T(a) = T(a-a) + T(a) + ca This implies infinite recursion, right?? since T(a) = T(a) + ... –  Mazyod Mar 25 '11 at 6:59
Indeed, and that makes it unusual. Did you come up with it? Because usually, both parts are fractions of n, which enables you to find an explicit formula for the recurrence, T(n/2) + T(n/2) for example. –  num3ric Mar 25 '11 at 10:11
yeah, I thought something was wrong .. This is actually an assignment in my algorithms class, and as always I decided to start a day before submitting, so I can't verify the "correctness" of the question itself ^^; .. many thanks. –  Mazyod Mar 25 '11 at 10:51
In the interest of people who may stumble upon this problem: Two possible issues with this approach - 1. When the substitution of n = a is made to determine T(a), we get this: T(a) = T(0) + T(a) + ca. Now, a>=1 and c>0, so we know right away that T(0) can't be 0 and that it is -ca to balance that equation. But of course once we do that, we merely have T(0) = -ca as the equation and nothing else. 2. We probably don't need to recurse T(a) because of the same difficulty the OP faced - it's a constant. Why do you want to establish a recurrence relation over a constant? –  user183037 Feb 7 '12 at 10:34
add comment

Your Answer


