Recursion or iteration (was Fibonacci series recursion error)

[Ian Kelly]

On Sat, May 14, 2011 at 11:24 AM, rusi <rustompmody 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).