I had an assignment in school last week to implement a function for calculating the n:th number in the fibonacci sequence. A 'sub-assignment' was to implement it using accumulation(Might not be a correct translation) in order to give the function O(n) time complexity. This all worked fine until I tried making the function (Int -> Integer). By experimenting a bit I realised that the time complexity was close to O(n^2) for really large numbers. It occurs to me that this must be because of the Integer implementation, which makes me a bit curious about how it works. I did a few Google searches and didn't find anything that seemed useful so I am turning to you guys in hope of either getting an explanation or a link that explains it thoroughly.
My code:
ackfib 0 = 0
ackfib 1 = 1
ackfib n = loop n 1 0 1
where
loop n n1 n2 i
| i < n = loop n (n1+n2) n1 (i+1)
| i == n = n1
| i > n = error "n must be greater than or equal to 0"
I am thankful for all answers
Viktor
This has nothing to do with Haskell really, it's just a result of the fact that the Fibonacci numbers grow exponentially quickly. Specifically, the nth Fibonacci number has about (log2 φ) n or roughly 0.48 n bits where φ is the golden ratio (1 + sqrt 5) / 2. Since addition of k-bit integers takes O(k) time, your O(n) additions actually take a total of O(n^2) time, because on average the numbers you're adding have O(n) bits.
(Note for sticklers: big O should really be big Theta in the above.)
To add to Reid's answer, the fact that your algorithm has O(N) time complexity depends on what you consider to be the step of execution. This is a common misconception of time complexity: that time complexity always corresponds to execution time.
What to consider the step depends on how deep we want to analyse the issue. If you define a step as one addition of Integer, yes, your algorithm with accumulators runs in O(N) time. If you define a step as one word addition (a 32- or 64-bit addition), it runs in O(N^2) as Reid explained.
If you want your complexity analysis to correspond to the execution time you need to use a step of execution whose execution time is bounded above by a constant, like the addition of two processor words. Addition of Integers is not, because Integers can be arbitrarily large.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With