python - Why does this memoisation function not run in linear time? -

i tried implement memoisation using arrays in recursive fibonacci function, fibmem() expecting runninng time come out o(n). initially, looked though had it, took faster regular recursive fibonacci function run. (red being regular fib() , green being fibmem())

but upon further inspection, (fibmem() represented red)

it looks though fibmem() runs in o(someconstant^n) time instead. here's code:

memo = [0] * 100 #initialise array argument = sys.argv[1]  def fibmem(n):          if n < 0:             return "no"          if n == 0 or n == 1:             memo[n] = 1             return memo[n]         if n not in memo:             memo[n] = fibmem(n-1) + fibmem(n-2)         return memo[n] 

now can fibmem() run in o(n) time using dictionaries instead of arrays in way:

memo = {0:1, 1:1}  argument = sys.argv[1]  def fibmem(n):          if n not in memo:             memo[n] = fibmem(n-1) + fibmem(n-2)         return memo[n] 

but think implementation using arrays similar. can't see why array implementation of fibmem() runs in exponential time. what's going on? how go fixing things?

the real problem isn't in operator scans list , takes linear time you're doing wrong.

your memo filled [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...]. when n example 40, , you're checking 40 not in memo, always fail, because 40 not fibonacci number. mean check whether 40-th fibonacci number has been computed, that's not @ you're checking. you're instead checking whether 40 (already computed) fibonacci number.

so shortcut whenever n happens fibonacci number, example @ 34. until 55, never such shortcuts, effectively disabling memoization entirely (in ranges). that's why exponential behavior there, non-memoized version earlier on.

also note striking interruption of curve between n=35 , n=36. that's not fluke, that's precisely because 34 fibonacci number. case n=36 goes n=35 , n=34, , because n=34 instant shortcut, n=35 part involves real work. that's why n=36 takes pretty exact same time n=35 (it was fluke took less when measured it).

instead of if n not in memo: should check if memo[n] == 0: or if not memo[n]:.

or instead, use dictionary: memo = {}. if n not in memo: it's supposed (because checks keys, not values). has advantage of not being limited.