en
th
‹ set
09
Fibonacci — the recursive trap
9 / 26
read the snippet · pick its Big-O
1
function
fib
(
n
)
{
2
if
(
n
<
=
1
)
return
n
;
3
return
fib
(
n
-
1
)
+
fib
(
n
-
2
)
;
4
}
O(1)
O(log n)
O(n)
O(n log n)
O(n²)
O(n³)
O(2^n)
O(n!)
⏵ submit
‹ prev · Find three discount codes that sum to a total
next · Fibonacci, but with a cache ›