1
vote
1answer
109 views

Stable algorithms from a backwards recurrence?

This is homework, so please only hints. We see that the recurrence $$I_n=\frac{1}{n}-\alpha I_{n-1}$$ can be used to compute the value of an integral, but the algorithm is unstable when $|\alpha ...
1
vote
1answer
50 views

How to approximate a complex linear homogenous recurrence with constant coefficients with a simple one?

Is there some standard way to approximate a complex linear homogenous recurrence with constant coefficients with a simple one? For example, I might want to approximate $$ ...
2
votes
0answers
61 views

On bounding the average cost of top-down merge sort

Let $A_n$ be the average number of comparisons to sort $n$ keys by merging them in a top-down fashion (see any algorithm textbook). It can he shown that $$ A_0 = A_1 = 0;\quad A_n = ...
10
votes
3answers
406 views

Solving randomized recurrence relation

I'm looking at the random sequence $x_n$ with $x_0=x_1=1$ and \begin{equation} x_{n+1}=2x_n\pm x_{n-1} \end{equation} where we choose the $\pm$ sign independently with equal probability. Now ...