Recursion or iteration (was Fibonacci series recursion error)

[Chris Angelico]

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