# Compute Recurrence Relation

• Sep 29th 2012, 10:56 PM
taleman
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
• Sep 30th 2012, 12:47 AM
chiro
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).
• Sep 30th 2012, 10:53 AM
taleman
Re: Compute Recurrence Relation
Quote:

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?
• Sep 30th 2012, 07:21 PM
chiro
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.
• Sep 30th 2012, 09:45 PM
MaxJasper
Re: Compute Recurrence Relation
Quote:

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{...}.$