Compute the n-th Fibonacci number in O(n) time, O(1) space
Implement fib(n) returning the n-th Fibonacci number (fib(0) = 0, fib(1) = 1). Requirements: O(n) time and O(1) extra space — iterate, do not use naive double recursion (exponential) and do not store the whole sequence. Handle the base case n < 2 by returning n.
func fib(n int) int {
// your code here
return 0
}Write the implementation.
Return n for n < 2, then keep two rolling values a, b := 0, 1 and update a, b = b, a+b in a loop from 2 to n, returning b. This is O(n) time, O(1) space — far better than naive recursion, which is exponential. A memoized recursion caches in a map[int]int.
- ✗Using naive double recursion, which is exponential time
- ✗Storing the whole sequence when two rolling variables suffice
- ✗Splitting
a, b = b, a+binto two statements, corrupting the update
- →Why does naive
fib(n-1) + fib(n-2)recursion run in exponential time? - →How does the parallel assignment
a, b = b, a+bavoid needing a temp variable?
Task
Compute the n-th Fibonacci number in O(n) time and O(1) space.
func fib(n int) int {
if n < 2 {
return n
}
a, b := 0, 1
for i := 2; i <= n; i++ {
a, b = b, a+b
}
return b
}Why iterative
Naive recursion fib(n-1) + fib(n-2) recomputes the same subproblems many times, giving exponential complexity (≈ O(φⁿ)).
The iterative version keeps only the last two values. On each step the parallel assignment a, b = b, a+b evaluates the right-hand side before writing, so no temp variable is needed. The result is O(n) time, O(1) space.
⚠️ If asked to memoize recursion, use a map[int]int cache so each fib(k) is computed once.
