A Leaner Fibonacci

Building Fibonacci from the bottom up brings fib down to $O(n)$ time, but it uses an array of $n+1$ integers. Look at what the loop reads. Each entry f[i] uses only the two entries just before it. Once the loop moves past those entries, they are never read again. So we do not really need the whole array. We only need the last two values. We can keep those two values in a pair of variables and compute the same answer:

public static int fib(int n) {
  if (n <= 1) {
    return n;
  }
  int prev = 0;
  int curr = 1;
  for (int i = 2; i <= n; i++) {
    int next = prev + curr;
    prev = curr;
    curr = next;
  }
  return curr;
}

Instead of a whole array, we keep a two-cell window that slides up the sequence. We start with the two known values:

       prev  curr
      ┌───┐ ┌───┐
start │ 0 │ │ 1 │
      └───┘ └───┘

Each pass computes next = prev + curr, then shifts the window forward by one. prev takes curr’s value and curr takes next’s. Here is the first pass, i = 2, computing next:

       prev  curr  next
      ┌───┐ ┌───┐ ┏━━━┓
i = 2 │ 0 │ │ 1 │ ┃ 1 ┃
      └───┘ └───┘ ┗━━━┛

And then shifting:

       prev  curr
      ┌───┐ ┏━━━┓
i = 2 │ 1 │ ┃ 1 ┃
      └───┘ ┗━━━┛

Every later pass does the same thing at the next index. By the final pass, curr holds the answer:

       prev  curr
      ┌───┐ ┏━━━┓
i = 5 │ 3 │ ┃ 5 ┃
      └───┘ ┗━━━┛

The loop still runs from 2 to n doing constant work each pass, so the time is still $O(n)$. The space changed. We now keep three variables, prev, curr, and next, and that count does not depend on $n$ at all. So the auxiliary space is $O(1)$.

Here is the cost of computing the same numbers three different ways:

Going from the first row to the second improved the time, and the space stayed the same. Going from the second row to the third improved the space, and the time stayed the same. A change to an algorithm can improve one cost without changing the other.