Hacker News Reader

It's log(n) multiplications, each of which requires something like O(n log n log log n) time [1]; so the actual complexity is O(n (log n)^2 log log n) ish.

[1] Schönhage-Strassen multiplication, one of many bignum multiplication algorithms with sub-quadratic complexity. Other algorithms in common use have worse asymptotic performance.

View on HN

Don't know why you were downvoted, you're absolutely correct. At first glance your n and my n are different, with mine (n1) being the input to the function and yours representing the number of digits in a multiplicand (n2). n1 and n2 are linearly related, though, since the exponentiation process increases the number of digits in a linear fashion.

It's also worth noting that since the Fibonacci sequence grows exponentially, the number of digits is the result will be linear in n. Therefore, the memory requirement is actually O(n), and writing the result to the screen will be O(n).

> At first glance your n and my n are different

Right; as you sketch out, there's some constants that disappear into the O() notation.

Reply on news.ycombinator.com