Re: Recursion or iteration (was Fibonacci series recursion error)

From	Mark Dickinson <dickinsm@gmail.com>
Newsgroups	comp.lang.python
Subject	Re: Recursion or iteration (was Fibonacci series recursion error)
Date	2011-05-15 12:29 -0700
Organization	http://groups.google.com
Message-ID	<cf8cc239-01cd-4b6b-8bdd-2d814b2f8e0b@b42g2000yqi.googlegroups.com> (permalink)
References	(10 earlier) <a69fa49f-4682-4828-890d-086e90f23ccd@l6g2000vbn.googlegroups.com> <71093cb7-3eb4-47f7-8936-2591cdaf4688@l2g2000prg.googlegroups.com> <mailman.1565.1305408027.9059.python-list@python.org> <e994a21a-7b9b-4227-8825-fce37c5c9912@17g2000prr.googlegroups.com> <be75129f-84f4-418e-a0ce-4fb120e1c55f@s14g2000vbi.googlegroups.com>

Show all headers | View raw

On May 15, 8:20 pm, Mark Dickinson <dicki...@gmail.com> wrote:
> On May 15, 4:32 am, rusi <rustompm...@gmail.com> wrote:
>
> > On May 15, 2:19 am, Ian Kelly <ian.g.ke...@gmail.com> wrote:
> > > Yup, linear.  Assuming you optimize the even case so that it doesn't
> > > actually call fib(n//2) twice, the call tree can be approximated as a
> > > balanced binary tree with height log(n).  The total number of nodes in
> > > the tree is thus O(2 ** log(n)) = O(n).
>
> > It would be linear if the base of the log were 2.
> > I am not sure it is.
> > You see the naive fib has a complexity which is fib itself. [Earlier
> > discussion with Steven]
> > fib is exponential but with radix < 2 [phi = (1 + sqrt(5))/2 ]
> > This would suggest that this algo is slightly better than linear.
>
> Nope.  It's linear, just as Ian Kelly said.  If g(n) is the total
> number of fib calls made for fib(n), then it's easy to show (e.g., by
> induction) that:
>
> (a) g(n) is an increasing function of n, and
> (b) g(2^k) = 2^k - 1 for all k >= 1.
>
> Hence g(n) is O(n).

Hmm.  It's even easier:  g(n) is:

  * 1 if n == 1
  * n if n > 1, n odd
  * n-1 if n > 1, n even

So definitely linear. :-)

--
Mark

Thread

Fibonacci series recursion error lalit <opposite800@gmail.com> - 2011-04-29 20:22 -0700
  Re: Fibonacci series recursion error Gary Herron <gherron@islandtraining.com> - 2011-04-29 20:41 -0700
  Re: Fibonacci series recursion error Jason Friedman <jason@powerpull.net> - 2011-04-30 03:57 +0000
  Re: Fibonacci series recursion error harrismh777 <harrismh777@charter.net> - 2011-04-29 23:45 -0500
    Re: Fibonacci series recursion error harrismh777 <harrismh777@charter.net> - 2011-04-29 23:51 -0500
      Re: Fibonacci series recursion error harrismh777 <harrismh777@charter.net> - 2011-04-30 00:31 -0500
        Re: Fibonacci series recursion error Peter Otten <__peter__@web.de> - 2011-04-30 08:14 +0200
          Re: Fibonacci series recursion error rusi <rustompmody@gmail.com> - 2011-05-02 00:08 -0700
    Re: Fibonacci series recursion error Hans Georg Schaathun <hg@schaathun.net> - 2011-04-30 06:50 +0100
    Re: Fibonacci series recursion error Paul Rudin <paul.nospam@rudin.co.uk> - 2011-04-30 06:43 +0100
  Re: Fibonacci series recursion error Ian Kelly <ian.g.kelly@gmail.com> - 2011-04-29 23:27 -0600
    Re: Fibonacci series recursion error harrismh777 <harrismh777@charter.net> - 2011-04-30 00:35 -0500
      Re: Fibonacci series recursion error Peter Otten <__peter__@web.de> - 2011-04-30 08:32 +0200
        Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-04-30 16:37 +1000
      Re: Fibonacci series recursion error Thomas Rachel <nutznetz-0c1b6768-bfa9-48d5-a470-7603bd3aa915@spamschutz.glglgl.de> - 2011-04-30 11:37 +0200
        Re: Fibonacci series recursion error harrismh777 <harrismh777@charter.net> - 2011-05-02 16:50 -0500
          Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-05-03 08:17 +1000
            Re: Fibonacci series recursion error harrismh777 <harrismh777@charter.net> - 2011-05-03 12:10 -0500
              Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-05-04 07:41 +1000
              Re: Fibonacci series recursion error Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-03 16:31 -0600
              Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-05-04 09:09 +1000
          Re: Fibonacci series recursion error Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-02 16:22 -0600
          Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-05-03 08:42 +1000
          Recursion or iteration (was Fibonacci series recursion error) rusi <rustompmody@gmail.com> - 2011-05-02 18:48 -0700
            Re: Recursion or iteration (was Fibonacci series recursion error) Chris Angelico <rosuav@gmail.com> - 2011-05-03 12:13 +1000
            Re: Recursion or iteration (was Fibonacci series recursion error) Chris Angelico <rosuav@gmail.com> - 2011-05-03 15:29 +1000
              Re: Recursion or iteration (was Fibonacci series recursion error) rusi <rustompmody@gmail.com> - 2011-05-03 00:52 -0700
                Re: Recursion or iteration (was Fibonacci series recursion error) Dave Angel <davea@ieee.org> - 2011-05-03 06:32 -0400
                Re: Recursion or iteration (was Fibonacci series recursion error) rusi <rustompmody@gmail.com> - 2011-05-03 03:51 -0700
                Re: Recursion or iteration (was Fibonacci series recursion error) Chris Angelico <rosuav@gmail.com> - 2011-05-03 21:04 +1000
                Re: Recursion or iteration (was Fibonacci series recursion error) Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-03 12:49 +0000
                Re: Recursion or iteration (was Fibonacci series recursion error) Chris Angelico <rosuav@gmail.com> - 2011-05-03 23:02 +1000
                Re: Recursion or iteration (was Fibonacci series recursion error) Hans Mulder <hansmu@xs4all.nl> - 2011-05-12 00:06 +0200
                Re: Recursion or iteration (was Fibonacci series recursion error) rusi <rustompmody@gmail.com> - 2011-05-13 04:11 -0700
                Re: Recursion or iteration (was Fibonacci series recursion error) Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-13 07:55 -0600
                Re: Recursion or iteration (was Fibonacci series recursion error) Hans Mulder <hansmu@xs4all.nl> - 2011-05-13 21:46 +0200
                Re: Recursion or iteration (was Fibonacci series recursion error) Mark Dickinson <dickinsm@gmail.com> - 2011-05-13 14:48 -0700
                Re: Recursion or iteration (was Fibonacci series recursion error) rusi <rustompmody@gmail.com> - 2011-05-14 10:24 -0700
                Re: Recursion or iteration (was Fibonacci series recursion error) Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-14 15:19 -0600
                Re: Recursion or iteration (was Fibonacci series recursion error) rusi <rustompmody@gmail.com> - 2011-05-14 20:32 -0700
                Re: Recursion or iteration (was Fibonacci series recursion error) Mark Dickinson <dickinsm@gmail.com> - 2011-05-15 12:20 -0700
                Re: Recursion or iteration (was Fibonacci series recursion error) Mark Dickinson <dickinsm@gmail.com> - 2011-05-15 12:29 -0700
            Re: Recursion or iteration (was Fibonacci series recursion error) Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-02 23:46 -0600

csiph-web