On Tue, 17 May 2011 10:02:21 -0700, geremy condra wrote: > or O(1): > > φ = (1 + sqrt(5)) / 2 > def fib(n): > numerator = (φ**n) - (1 - φ)**n > denominator = sqrt(5) > return round(numerator/denominator)
I'd just like to point out that, strictly speaking, it's only O(1) if you assume that exponentiation is O(1). Computer scientists often like to make this simplifying assumption, and it might even be true for floats, but for long ints and any numeric data types with unlimited precision, it won't be. -- Steven -- http://mail.python.org/mailman/listinfo/python-list
