|
|
|
|
|
|
by yaks_hairbrush
3514 days ago
|
|
|
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). |
|
|
Right; as you sketch out, there's some constants that disappear into the O() notation.