On May 15, 8:20 pm, Mark Dickinson <dicki...@gmail.com> wrote: > On May 15, 4:32 am, rusi <rustompm...@gmail.com> wrote: > > > On May 15, 2:19 am, Ian Kelly <ian.g.ke...@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).
Hmm. It's even easier: g(n) is: * 1 if n == 1 * n if n > 1, n odd * n-1 if n > 1, n even So definitely linear. :-) -- Mark -- http://mail.python.org/mailman/listinfo/python-list
