Recursion or iteration (was Fibonacci series recursion error)

[Mark Dickinson]

On May 15, 8:20 pm, Mark Dickinson <dicki... at gmail.com> wrote:
> On May 15, 4:32 am, rusi <rustompm... at gmail.com> wrote:
>
> > On May 15, 2:19 am, Ian Kelly <ian.g.ke... at 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