First thing I recommend is to look at this in terms of k's and k+1 instead of the n's and then look at the recurrence relation in terms of T(k) and T(k+1) or T(k-1).
I understand how to solve recurrence relations, however when given a problem like the one below I'm not sure what I need to do.
I've searched google but all I ever find is how to solve the recurrence relation not how to compute like the problem below. Can someone please
explain it too me? Thank you.
Compute T(n) for n = 2^k
T(n) = a for n ≤ 2
T(n) = 8T(n/2) + bn^2 for n > 2
What I mean is to get the sequence in terms of successive integer values rather than in exponential values (which it is currently in). So in other words get T(b) in terms of T(b+1) or T(b-1) or T(b+x) where x is an integer: getting it into this form allows you to look at the expansion in terms of simple integers and then once you get it in terms of T(n) for a general integer n, you can back-substitute in terms that exponential form and get it in terms of how it was given originally.
You are given n = 2^k but this is not in integer form, so instead of looking at T(n) in terms of T(n/2), it makes more sense to look at T(b) in terms of T(b+1) or in terms of T(b+n) for some natural number n.