[orlandu63]

In the same vein, there's also an O(log(fib(n))) recursive algorithm:

    fib :: Integer -> Integer
    fib 0 = 0
    fib 1 = 1
    fib 2 = 1
    fib n = case n `quotRem` 2 of
        -- if n = 2*m
        (m,0) -> (fib (m+1))^2 - (fib (m-1))^2

        -- if n = 2*m + 1
        (m,1) -> (fib (m+1))^2 + (fib (m  ))^2

[shrughes]

Why not just say O(n)?

[orlandu63]

Fake answer: because O(log(fib(n))) conveys more information as to how the algorithm works.

Real answer: because I didn't realize that it's equivalent to O(n).