Integer time complexity in Haskell

Question

Hello!

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

Answer 1

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.