# linear vs non-linear recursion

• May 20th 2010, 12:44 AM
Aileys.
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
• May 22nd 2010, 08:40 PM
Haven
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.
• May 22nd 2010, 10:29 PM
CaptainBlack
Quote:

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
• May 23rd 2010, 03:47 PM
Aileys.