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.
Related concepts
- multiple recursionproduced by · Multiple recursion is recursion in which one invocation makes more than one recursive call.
- 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.
- 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.
- performancemeasures · Performance is the measurable effectiveness or operational behavior of a system under specified conditions, assessed through relevant qualities such as task results, speed, responsiveness, throughput, or resource use.
- 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.
- recursionmeasured by · Recursion is a computational technique in which a definition or procedure refers to or invokes the same definition or procedure, directly or indirectly.
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.