<br><div class="gmail_quote">On Mon, May 2, 2011 at 10:29 PM, Chris Angelico <span dir="ltr"><<a href="mailto:rosuav@gmail.com">rosuav@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<div class="im">On Tue, May 3, 2011 at 3:27 PM, Dan Stromberg <<a href="mailto:drsalists@gmail.com">drsalists@gmail.com</a>> wrote:<br>
><br>
> But the recursive solution has time complexity of O(logn).  The iterative<br>
> solution has time complexity of O(n).  That's a significant difference for<br>
> large n - a significant benefit of the recursive version.<br>
<br>
</div>Are you sure? It will produce n function calls and n multiplications,<br>
how is that O(log n)?<br></blockquote><div><br>Doh.<br><br>Usually when someone gives a recursive solution to this problem, it's O(logn), but not this time.<br><br>Here's a logn one:<br><span class="gI"><span class="gD" style="color: rgb(0, 104, 28);"><br>
</span><span class="go"></span></span> def power(x, n):<br>   if n == 0:<br>      return 1<br>   else:<br>      half, remainder = divmod(n, 2)<br>      if remainder == 1:<br>         return power(x, half) ** 2 * x<br>      else:<br>
         return power(x, half) ** 2<br><br></div></div>