On May 15, 2:19 am, Ian Kelly <ian.g.ke...@gmail.com> wrote: > 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).
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. -- http://mail.python.org/mailman/listinfo/python-list
