Exponential time complexity

As explained in 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.

Exponential time complexity describes running time that grows exponentially with input size. Exact solutions can become impractical quickly, even when each candidate is straightforward to check. section 17.2

Traveling-salesman planning

For delivery routing, an exact algorithm may examine possible city sequences. Ten cities already produce about 3.6 million sequences, 15 produce about 1.3 trillion, and 20 produce about 2.4 × 10^18. Even an exponential algorithm that improves asymptotically on factorial enumeration may handle only around 40 deliveries, or fewer in practice. section 17.2

Figure 17.8 An example map, mixing the DC Universe’s cities and other real ones, with some distances: because this is a complete graph with close to fifty edges, we are only showing a few numbers, almost only for the edges in the best tour (the thicker edges).

Use the route map to connect city count, candidate tours, and the practical limits of exact optimization. section 17.2

How Advanced Algorithms and Data Structures covers it

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.

How it connects

Connects traveling-salesman problem with NP-completeness, NP-hardness, polynomial-time verification, and P versus NP.

liveBookmanning.com

Read Advanced Algorithms and Data Structures on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Modern C, Third EditionExponential computation time is runtime whose growth as input size increases is bounded by an exponential function.
• 

  liveBookmanning.com
  Fabulous Adventures in Data Structures and AlgorithmsAn exponential-time algorithm has a running time that grows exponentially with input size.

Compare how 3 books explain exponential time complexity →

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.

This explainer was generated by Manning's knowledge graph from the text of Advanced Algorithms and Data Structures. The section links point to the parts of the book it draws on.