int rec_fib[MAX_N]; int fib(int n) { if (n <= 1) return n; if (rec_fib[n] != 0) return rec_fib[n]; return fib(n-1) + fib(n-2); }
O(φⁿ), φ=(√5+1)/2
O(2ⁿ)
O(n²)
O(n)