We were asked the following question in our exam:
Solve or bound the recurrence
T(n) = 2T(n − 3) for
T(1) = T(2) = T(3) = 1.
How do I go about solving this type of recurrence? For a normal recurrence of the form
T(n) = 2T(n - 3) + cn, I would have considered
cn to be the root and then solved the remainder of the tree. However, since the constant term is missing here, it means that the work done in each recursive call is 0. So, what would be the time complexity? Is my understanding incorrect?
Thanks for you help!
P.S.: This is not this, because this one has the constant term missing.