Thread: linear vs non-linear recursion

Hi there,

I'm reading a book that considers two different methods to obtain a recursive formula for something. One method produces a non-linear recursion and the other produces a linear one. The authors comment that a difficulty with the first one is that it is non-linear - and this motivates the second method.

Why would a linear recursion be so much more preferable over a non-linear one? Is there a significant increase in computational load for the non-linear one? Or what?

Thanks

Linear recursion is in time, which means if we have do to n operations, the time it takes to do the operation will be a multiple of n.
But non linear recursion will have much larger time. Like , or .
So doing n operations will take much longer than linear recursion.

We, prefer linear recursion because not only does it not take a long, but chances are if is much more efficient.

Originally Posted by Aileys.

Hi there,

I'm reading a book that considers two different methods to obtain a recursive formula for something. One method produces a non-linear recursion and the other produces a linear one. The authors comment that a difficulty with the first one is that it is non-linear - and this motivates the second method.

Why would a linear recursion be so much more preferable over a non-linear one? Is there a significant increase in computational load for the non-linear one? Or what?

Thanks

A linear recursion has a closed form solution that we know how to find, there is no guarantee that is true for a non-linear one and if it were it does not mean it is easy to find or that anyone knows how.

CB

Thanks, that's very helpful.