Question about solving recurrences/difference equations

  • Thread starter homomorphism
  • Start date
In summary, the WolframAlpha engine used to get the answer used the z-transform to solve the http://www09.wolframalpha.com/input/?i=f%282*m%29%3D2*f%28m%29%2B2*m%2C+f%281%29%3D1.
  • #1
homomorphism
19
0
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.
 
Physics news on Phys.org
  • #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
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
homomorphism said:
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:

1. What is a recurrence/difference equation?

A recurrence or difference equation is a mathematical equation that describes a sequence of values, where each value is dependent on the previous values in the sequence. It is commonly used to model and solve problems in various fields such as economics, physics, and computer science.

2. How do you solve a recurrence/difference equation?

There are several methods for solving recurrence/difference equations, including substitution, iteration, and generating functions. The specific method used will depend on the complexity of the equation and the desired solution. It often involves finding a closed-form solution or a recursive formula for the sequence.

3. What is the difference between a recurrence and a difference equation?

A recurrence equation is a type of difference equation that describes a sequence of values in terms of previous values in the sequence. On the other hand, a difference equation can also describe a relationship between consecutive terms in a sequence, but it may not necessarily depend on the previous values in the sequence.

4. Can recurrence/difference equations be solved analytically?

In some cases, recurrence/difference equations can be solved analytically by finding a closed-form solution. However, for more complex equations, numerical methods may be required to find an approximate solution.

5. What are some real-world applications of solving recurrence/difference equations?

Recurrence/difference equations have numerous real-world applications, such as predicting population growth, modeling the spread of diseases, analyzing financial markets, and optimizing resource allocation in computer networks. They are also used in computer algorithms and data structures, such as the Fibonacci sequence and the Tower of Hanoi problem.

Similar threads

Replies
1
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
797
  • Differential Equations
Replies
7
Views
2K
  • Differential Equations
Replies
3
Views
2K
  • Differential Equations
Replies
1
Views
1K
  • Differential Equations
Replies
7
Views
334
  • Set Theory, Logic, Probability, Statistics
Replies
18
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
22
Views
4K
  • Differential Equations
Replies
1
Views
707
Replies
3
Views
740
Back
Top