Find the nth Fibonacci number iteratively in O(n) time, O(1) space
Implement Fib(n) returning the nth Fibonacci number with Fib(0) == 0 and Fib(1) == 1. Requirements: ITERATIVE, O(n) time and O(1) space — keep only the last two values, do NOT use naive recursion (which is exponential) and do NOT allocate an array of all n values.
public static long Fib(int n)
{
// your code here
return 0;
}Write the implementation.
Keep two rolling values a = 0, b = 1. Loop n times: compute b as a + b and shift a to the old b via a tuple update (a, b) = (b, a + b). Return a. This is O(n) time, O(1) space — no array and no exponential recursion.
- ✗Using naive double recursion, which is exponential O(2^n), not O(n)
- ✗Allocating an array of all n values, wasting O(n) space when O(1) suffices
- ✗Off-by-one in the loop so
Fib(0)orFib(1)returns the wrong seed value
- →Why is naive recursion exponential, and how does memoization fix it?
- →At what
ndoesFiboverflowlong?
Task
Return the nth Fibonacci number iteratively in O(n) time and O(1) space.
public static long Fib(int n)
{
long a = 0, b = 1; // Fib(0), Fib(1)
for (int i = 0; i < n; i++)
(a, b) = (b, a + b); // slide the pair forward
return a;
}How it works
Each Fibonacci number is the sum of the two before it. Instead of storing the whole sequence, we keep only the pair (a, b) = two adjacent numbers, starting at (Fib(0), Fib(1)) = (0, 1).
Each iteration slides the window forward: the new a becomes the old b, and the new b becomes the sum a + b. The tuple update (a, b) = (b, a + b) does both assignments at once, with no temporary variable. After n steps, a holds Fib(n).
The loop runs n times with constant work per step — O(n) time and O(1) space. Naive recursion Fib(n-1) + Fib(n-2) would be exponential O(2ⁿ), recomputing the same values over and over.
