Trouble with Recurrence Relations?

  • Thread starter deedex11
  • Start date
  • #1
1
0
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!!
 

Answers and Replies

  • #2
tiny-tim
Science Advisor
Homework Helper
25,832
251
welcome to pf!

hi deedex11! welcome to pf! :smile:

(try using the X2 icon just above the Reply box :wink:)
t(n) = 5t(n/2) + n
this is a weird recurrence relation since it doesn't go from n to n + 1 :frown:

you need to make it do that!

so, for each odd whole number A, there's a sequence {A2m}, 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(A2m) = 5t(A2m-1) + A2m :wink:
 
Last edited:
  • #3
828
2


hi deedex11! welcome to pf! :smile:

(try using the X2 icon just above the Reply box :wink:)


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

you need to make it do that!

so, for each odd whole number A, there's a sequence {A2m}, 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(A2m) = 5t(A2m-1) + A2m :wink:
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.
 

Related Threads on Trouble with Recurrence Relations?

  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
0
Views
3K
Replies
8
Views
2K
  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
0
Views
1K
Top