Exponential time complexity describes runtime that grows exponentially with input size. Naive recursive Fibonacci computation repeatedly solves the same subproblems, making execution time proportional to a constant times φⁿ. section 7.3
Naive recursive Fibonacci
The function fib(n) calls fib(n−1) and fib(n−2) for each n above two. Its call tree contains repeated work, such as computing fib(2) twice when evaluating fib(4), so execution time becomes impractical as n increases. section 7.3
size_t fib(size_t n) [[__unsequenced__]] {
if (n < 3)
return 1;
else
return fib(n-1) + fib(n-2);
}
Inspect the compact C implementation whose two recursive calls produce exponential computation time. section 7.3
Avoid repeated subproblem computation by changing the algorithm:
- Cache previously computed Fibonacci values, trading storage for linear execution time. section 7.3
- Recognize that algorithmic improvement can matter more than platform-specific implementation cleverness. section 7.3
