Trouble with Recurrence Relations?

[deedex11]

1. I am trying to practice solving recurrence relations but get stuck when it comes to generalizing the last part of them and would be grateful if someone could offer some help. I'm not very good with series which is why I may be having some problems with them. Here are a few examples if its easier for you to explain with an example (these aren't homework questions, just random ones takes from a book):



2. t(n) = 5t(n/2) + n
t(n) = t(n/2) + 3logn
t(n) = 2t(n/2) + n^2



3. for the first one i tried to unroll it and have come up with 5^nt(1) + (5^n)/n(nlogn) + n. but this could be totally wrong. any help appreciated!

 

[tiny-tim]

welcome to pf!

hi deedex11! welcome to pf!

(try using the X² icon just above the Reply box )

t(n) = 5t(n/2) + n

this is a weird recurrence relation since it doesn't go from n to n + 1

you need to make it do that!

so, for each odd whole number A, there's a sequence {A2^m}, and the sequences for different As don't overlap, so you'll solve each sequence separately, with its own independent initial condition (and constant)

in other words, solve t(A2^m) = 5t(A2^m-1) + A2^m

 

[Robert1986]

hi deedex11! welcome to pf!

(try using the X² icon just above the Reply box )


this is a weird recurrence relation since it doesn't go from n to n + 1

you need to make it do that!

so, for each odd whole number A, there's a sequence {A2^m}, and the sequences for different As don't overlap, so you'll solve each sequence separately, with its own independent initial condition (and constant)

in other words, solve t(A2^m) = 5t(A2^m-1) + A2^m

I don't see how the T(n/2) makes this odd; especially considering the fact that it seems as though he is more concerned with an asymptotic analysis than an actual answer. The relation in question can be "solved" using the Master Theorem.