13 lines
638 B
Plaintext
13 lines
638 B
Plaintext
Fibonacci: how many calls does each approach make?
|
|
==================================================
|
|
|
|
n fib(n) naive calls memo calls table steps
|
|
10 55 177 19 9
|
|
20 6765 21891 39 19
|
|
30 832040 2692537 59 29
|
|
40 102334155 331160281 79 39
|
|
|
|
naive calls = every call the recursion made (counted, not predicted).
|
|
memo calls = the same recursion with a notebook: 2n-1 calls, because each F(k) is computed once.
|
|
table steps = additions in the bottom-up loop (n-1).
|