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.(adsbygoogle = window.adsbygoogle || []).push({});

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.

**Physics Forums | Science Articles, Homework Help, Discussion**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Question about solving recurrences/difference equations

Loading...

Similar Threads for Question solving recurrences |
---|

I Question about second order linear differential equations |

B Simple double integration of square wave question |

I Question regarding integration of an equation |

A Some questions regarding the ADI Method |

I Quick Differential Form Question |

**Physics Forums | Science Articles, Homework Help, Discussion**