Recursion or iteration (was Fibonacci series recursion error)

Chris Angelico rosuav at gmail.com
Tue May 3 01:29:51 EDT 2011


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)?

Chris Angelico



More information about the Python-list mailing list