1. ## Compute Recurrence Relation

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

2. ## Re: Compute Recurrence Relation

Hey taleman.

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).

3. ## Re: Compute Recurrence Relation

Originally Posted by chiro
Hey taleman.

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).
not sure I understand, so I should sun n for k, then k-1, then k-2 etc?

4. ## Re: Compute Recurrence Relation

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.

5. ## Re: Compute Recurrence Relation

Originally Posted by taleman
Compute T(n) for n = 2^k
T(n) = a for n ≤ 2
T(n) = 8T(n/2) + bn^2 for n > 2
$T\left(2*2^k\right)=2^{2 k-2}\left[2^{k-2}a+\left(2^k-1\right)b\right]$......... $k=0,1,2,3,\text{...}.$