Functional recurrence on a constant?
-
11-11-2019 - |
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