Recursion or iteration (was Fibonacci series recursion error)

[rusi]

On May 15, 2:19 am, Ian Kelly <ian.g.ke... at gmail.com> wrote:
> On Sat, May 14, 2011 at 11:24 AM, rusi <rustompm... at gmail.com> wrote:
> > def fib(n):
> >    if n==1 or n==2:
> >        return 1
> >    elif even(n):
> >        return sq(fib (n//2)) + 2 * fib(n//2) * fib(n//2 - 1)
> >    else:
> >        return sq(fib (n//2 + 1)) + sq(fib(n // 2))
>
> > This is a strange algo  -- logarithmic because it halves the n,
> > exponential because of the double (triple) calls.  [I cannot say I
> > know how to work out its exact complexity but I would guess its about
> > linear]
>
> 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.

But I have no idea of the exact complexity.