On Mon, May 2, 2011 at 11: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.
It's linear as written. I think you're talking about an
implementation like this one:
def powR(x,n):
if n < 0:
return 1.0 / powR(x, -n)
elif n == 0:
return 1
else:
half_n = n // 2
root = powR(x, half_n)
result = root * root
if half_n + half_n == n - 1:
result = result * x
return result
That's O(log n), but it was harder to write, and it could just as
easily be iterative. In fact it might actually have been a bit
simpler to write it iteratively.
--
http://mail.python.org/mailman/listinfo/python-list
