Question

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 − a) + T (a) + cn
T (n) = T (n -2a) + T (a) + ????

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top