1

As I learnt in SICP, tree recursion's complexity grows exponentially with n. If in Haskell I wrote like,

fib n | n <= 1 = n
      | otherwise = fib (n-1) + fib (n-2)

Is it true that, since Haskell is lazy, it calculate fib 1, fib 2... all once, so the complexity is linear with n?

ljedrz
  • 20,316
  • 4
  • 69
  • 97
Xiaojun Chen
  • 1,222
  • 2
  • 12
  • 21
  • 2
    Possible duplicate of [Memoization in Haskell?](http://stackoverflow.com/questions/3208258/memoization-in-haskell) – Alec Sep 01 '16 at 00:43
  • 5
    No, Haskell does not memoize functions. See something like [this](http://stackoverflow.com/questions/11466284/how-is-this-fibonacci-function-memoized). Note that further complications for memoization also arise from polymorphic code ([this](http://stackoverflow.com/questions/38879778/does-haskell-frege-ever-recalcuate-elements-of-a-lazy-list/38880106#38880106) question is sort of relevant) – Alec Sep 01 '16 at 00:49
  • 2
    If you want that *function*, you should use exponentiation of matrices by squaring. That's considerably faster than linear time would be, even if you'd achieved it. – dfeuer Sep 01 '16 at 07:02
  • @dfeuer Technically that's still O(n). Sure, doing O(log n) multiplications + additions has probably smaller constants than the naive solution with n additions, but both do O(n) bit operations. – Bakuriu Sep 01 '16 at 09:59
  • @dfeuer You mean the Exercise 1.19 of SICP – Xiaojun Chen Sep 01 '16 at 10:27
  • @Bakuriu, by that standard, the list approach isn't even linear, is it? – dfeuer Sep 01 '16 at 13:40
  • @Bakuriu, also, does your statement continue to hold if one uses extremely fancy multiplication algorithms (e.g., Fourier transform ones)? – dfeuer Sep 01 '16 at 13:51
  • I don't have SICP in front of me, Xiaojun Chen, so I don't know. – dfeuer Sep 01 '16 at 13:52
  • @dfeuer The number of bits in fibonacci numbers is O(n) (they grow exponentially), that's pretty definitive regarding the lower bound complexity to compute them, that was my point. – Bakuriu Sep 01 '16 at 14:04
  • @Bakuriu, right, I forgot just how fast they go. Are you sure the naive approach of doing `n` additions is O(n)? – dfeuer Sep 01 '16 at 14:06

1 Answers1

3

Debug.Trace can give the number of times fib is called :

import Debug.Trace

fib :: Int -> Int
fib n = trace "CALL" $ case n of
  0 -> 0
  1 -> 1
  _ -> fib (n-1) + fib (n-2)

For fib 5, it prints CALL 15 times, so it's not O(n).

V. Semeria
  • 3,128
  • 1
  • 10
  • 25