Efficient program for Fibonacci numbers

Write a function that returns the $n$th Fibonacci number, and comment on its efficiency.

Iterate with two running values: $O(n)$ time, $O(1)$ space. The naive recursion $F(n)=F(n-1)+F(n-2)$ recomputes subproblems and takes exponential time. Looping upward (or memoising) is linear, and $2\times2$ matrix powering or fast-doubling gets $O(\log n)$ arithmetic operations. Watch overflow: a signed 64-bit integer only holds values up to $F_{92}$.