Exponential time complexity
Exponential time complexity is a computational growth rate in which an algorithm’s running time increases exponentially with input size.
Modern C, Third Edition
Exponential computation time is runtime whose growth as input size increases is bounded by an exponential function.
- How it is used
- Uses recursive Fibonacci to show why repeated subproblems can make an algorithm impractical.
- How deep it goes
- Derives a recurrence and φⁿ bound, then contrasts exponential recursion with cached linear computation.
- Examples
- Uses naive fib, the fib(4) call tree, fibCache, and a constant-length-buffer implementation.
- What you can do after
- Diagnose repeated recursive work and apply caching to reduce Fibonacci computation from exponential to linear time.
Read how Modern C, Third Edition explains exponential time complexity →
Advanced Algorithms and Data Structures
An exponential-time algorithm has a running time that grows exponentially with the size of its input in the worst case.
- How it is used
- Frames why exact traveling-salesman planning requires advance computation when the number of cities grows.
- How deep it goes
- Quantifies exponential growth against factorial enumeration but stops short of deriving a specific exponential algorithm.
- Examples
- Uses delivery routes with 10, 15, and 20 cities to show rapidly expanding candidate counts.
- What you can do after
- Evaluate when exact optimization becomes impractical and when planning or precomputation is necessary.
Read how Advanced Algorithms and Data Structures explains exponential time complexity →
Fabulous Adventures in Data Structures and Algorithms
An exponential-time algorithm has a running time that grows exponentially with input size.
- How it is used
- Frames graph coloring as a practical setting where exponential search remains useful with effective branch reduction.
- How deep it goes
- Defines exponential algorithms through backtracking behavior and contrasts them with polynomial algorithms, without proving complexity bounds.
- Examples
- Uses graph coloring with recursive color guesses, partial assignments, broken results, complete solutions, and reducer-based pruning.
- What you can do after
- Evaluate exponential search by identifying recursive branching and recognizing how reduction can make practical instances manageable.
Also covered in
What to know first
- fixed-size arrayA fixed-size array is an indexed collection whose storage capacity or length is established when it is created and remains unchanged.
Related concepts
- multiple recursionproduced by · Multiple recursion is recursion in which one invocation makes more than one recursive call.
- catastrophic backtrackingproduced by · Catastrophic backtracking is pathological regular-expression matching in which ambiguous alternatives cause exponentially many paths to be explored, potentially causing extreme execution time.
- machine learningmeasured by · Machine learning is a field of computational methods in which systems learn patterns or relationships from data to make predictions, decisions, or other outputs.
- time complexitykind of · Time complexity describes how an algorithm’s execution time grows as a function of its input size or parameters.
- performancemeasures · Performance is a measure of how effectively a person, process, model, or system achieves its objectives, including qualities such as output quality, speed, and resource efficiency.
- Traveling Salesman problemused by · The Traveling Salesman problem is a combinatorial optimization problem that seeks a minimum-cost tour visiting each specified location exactly once and returning to the starting location.
Questions about exponential time complexity
What is exponential time complexity?
Exponential time complexity is a computational growth rate in which an algorithm’s running time increases exponentially with input size.
Which Manning books explain exponential time complexity?
Modern C, Third Edition, Advanced Algorithms and Data Structures and Fabulous Adventures in Data Structures and Algorithms.
What should I know before learning exponential time complexity?
Manning books that teach exponential time complexity usually introduce fixed-size array first.
What is exponential time complexity a kind of?
Exponential time complexity is a kind of time complexity. Time complexity describes how an algorithm’s execution time grows as a function of its input size or parameters.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.


