Question about solving recurrences/difference equations

  • #1

Main Question or Discussion Point

i want to know if there's any standard symbolic method of solving recurrences often found in the analysis of algorithms. many of these recurrences are readily solved by the master theorem. let's say we don't want to use that (for whatever reason) and we don't want to draw recursion trees.

let's take for example:
T(n) = 2T(n/2) + n

how exactly would we put this in difference equation form? something like T[i+1] = kT + n? k is some constant (basically some function on the 2) after we do that it is straightforward (i think) to use some symbolic differentiation and then solve the recurrence. We should be getting nlogn (log base 2) as the solution to this recurrence. but i don't think i'm writing down the actual difference equation correctly.
 

Answers and Replies

  • #2
Let n=2i

T(n) = 2T(n/2) + n will gives T(2i) = 2T(i) + 2i.

How am I going to expressed this as T[i+1] = kT + n ? :confused:
 
  • #3
703
13
For T(n) = 2T(n/2) + n you can set [itex]n=2^k[/itex]
Then you have [itex]T(2^k) = 2T(2^{k-1}) + 2^k[/itex]. I don't know if that helps.
 
  • #4
Wow that's good idea Edgardo. So what do we do next to solve T(n) = 2T(n/2) + n ?

May be we need to use z-transform or Fourier transform directly.
 
  • #5
i want to know if there's any standard symbolic method of solving recurrences often found in the analysis of algorithms. many of these recurrences are readily solved by the master theorem. let's say we don't want to use that (for whatever reason) and we don't want to draw recursion trees.

let's take for example:
T(n) = 2T(n/2) + n

how exactly would we put this in difference equation form? something like T[i+1] = kT + n? k is some constant (basically some function on the 2) after we do that it is straightforward (i think) to use some symbolic differentiation and then solve the recurrence. We should be getting nlogn (log base 2) as the solution to this recurrence. but i don't think i'm writing down the actual difference equation correctly.


Let n=2m.
T(n) = 2T(n/2) + n will gives T(2m) = 2T(m) + 2n.

I have just come to know about WolframAlpha at Sticky: WolframAlpha guide on electrical engineering forum.
Solving the http://www09.wolframalpha.com/input/?i=f(2*m)=2*f(m)+2*m,+f(1)=1", and simplify (assuming T(1)=1 )

T(2n) = 2nlog2n + 4n.

What method does the WolframAlpha engine used to get the answer?
 
Last edited by a moderator:

Related Threads for: Question about solving recurrences/difference equations

Replies
3
Views
683
Replies
0
Views
2K
Replies
1
Views
596
Replies
2
Views
937
Replies
2
Views
876
Top