On Mon, May 2, 2011 at 10:29 PM, Chris Angelico <ros...@gmail.com> wrote:
> On Tue, May 3, 2011 at 3:27 PM, Dan Stromberg <drsali...@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
--
http://mail.python.org/mailman/listinfo/python-list
