Results 1 to 4 of 4

Math Help - linear vs non-linear recursion

  1. #1
    Junior Member
    Joined
    Jun 2009
    Posts
    33

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member Haven's Avatar
    Joined
    Jul 2009
    Posts
    197
    Thanks
    8
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Aileys. View Post
    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Jun 2009
    Posts
    33
    Thanks, that's very helpful.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 7
    Last Post: October 10th 2011, 04:06 PM
  2. Replies: 1
    Last Post: August 1st 2011, 11:00 PM
  3. non homogeneous linear recursion
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 6th 2010, 12:59 AM
  4. Replies: 5
    Last Post: September 6th 2010, 04:55 PM
  5. Replies: 7
    Last Post: August 30th 2009, 11:03 AM

Search Tags


/mathhelpforum @mathhelpforum