# Thread: linear vs non-linear recursion

1. ## 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

2. Linear recursion is in $\mathcal{O}(n)$ 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 $\mathcal{O}(n^t)$, $\mathcal{O}(n!)$ or $\mathcal{O}(n\log{n})$.
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.

3. 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

4. Thanks, that's very helpful.