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

Taught in

References