Recursion or iteration (was Fibonacci series recursion error)

[Dan Stromberg]

On Mon, May 2, 2011 at 10:29 PM, Chris Angelico <rosuav at gmail.com> wrote:

> On Tue, May 3, 2011 at 3:27 PM, Dan Stromberg <drsalists at gmail.com> wrote:
> >
> > But the recursive solution has time complexity of O(logn).  The iterative
> > solution has time complexity of O(n).  That's a significant difference
> for
> > large n - a significant benefit of the recursive version.
>
> Are you sure? It will produce n function calls and n multiplications,
> how is that O(log n)?
>

Doh.

Usually when someone gives a recursive solution to this problem, it's
O(logn), but not this time.

Here's a logn one:

def power(x, n):
   if n == 0:
      return 1
   else:
      half, remainder = divmod(n, 2)
      if remainder == 1:
         return power(x, half) ** 2 * x
      else:
         return power(x, half) ** 2
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20110502/acbbf0a9/attachment-0001.html>