On Sat, May 14, 2011 at 11:24 AM, rusi <rustompm...@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). -- http://mail.python.org/mailman/listinfo/python-list