exponential time
Work that roughly doubles each time the input grows by one, written O(2^n), which becomes impossible to finish for even modest inputs.
In more detail
Naive recursive Fibonacci is exponential because each call spawns two more calls that repeat the same work. Exhaustive search over all subsets of n items is also exponential. Dynamic programming and pruning are the usual ways to escape it.
Related terms
- growth rate — The rule that says how fast an algorithm's cost rises as the input size n rises, such as constant, linear or quadratic.
- dynamic programming — A technique that solves a problem by breaking it into overlapping subproblems, solving each only once and storing the answers for reuse.
- pruning — Abandoning a branch of a search as soon as a check shows it cannot lead to a valid or better solution.
- Fibonacci sequence — The number sequence 0, 1, 1, 2, 3, 5, 8, and so on, where each number is the sum of the two before it.
Taught in
- Dynamic Programming: Memoisation And Tabulation — Algorithms & Data Structures for Working Engineers