Recursion or iteration (was Fibonacci series recursion error)

[Mark Dickinson]

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

Mark