Exponential

As explained in Grokking Data Structures

Exponential growth is growth proportional to a fixed base raised to a power that increases with input size.

Exponential growth accelerates dramatically as the input grows. Functions such as 2^n and 5^n + 2 may look manageable for small inputs, then skyrocket for larger ones. section 4.8

In algorithm analysis, exponential growth means:

• Small inputs are often manageable, but the required time or memory can become enormous quickly. section 4.9
• Values such as 2^n already become huge when n is greater than 30. section 4.16
• Exponential functions grow much faster than linear, linearithmic, or polynomial functions. section 4.8

Generating every subset

An algorithm that computes every subset of an array faces exponential growth. With 60 elements, the work could take centuries; with 100 elements, it reaches the order of magnitude of the age of the universe. This is why such algorithms are practical only for small arrays. section 4.9 section 4.16

Some of the growth rates you might encounter when studying algorithms. From left to right, the functions grow increasingly faster.

Use the growth-rate figure to compare exponential curves with slower classes and see how quickly their values separate. section 4.8

How long does it take to run an algorithm? That depends on the order of growth of its running time. All results are approximated.

Use the running-time figure to connect exponential growth with practical execution times as input sizes increase. section 4.9

How Grokking Data Structures covers it

How deep it goes

Compares growth rates and practical scale, but stops short of deriving exponential functions or implementing them.

Examples

Uses 2^n, 5^n + 2, all array subsets, and input sizes of 60 and 100 elements.

What it assumes

Assumes familiarity with input size and algorithm resources while introducing exponential growth through comparisons and examples.

What you can do after

Evaluate whether an algorithm remains practical as its input grows, especially when it processes all subsets.

How it connects

Connects exponential growth with Big-O notation, running time, memory usage, and generating subsets.

liveBookmanning.com

Read Grokking Data Structures on liveBook Get the book at manning.com

Related concepts

• softmaxused by · Softmax is a function that exponentiates a vector of scores and normalizes the results into nonnegative values that sum to one.
• Taylor seriesuses · A Taylor series is a power series whose coefficients are determined by a function’s derivatives evaluated at a specified expansion point.
• polynomial regressionaddressed by · Polynomial regression is a regression method that models an outcome as a polynomial function of one or more input variables.
• exponential time complexitymeasures · Exponential time complexity is a computational growth rate in which an algorithm’s running time increases exponentially with input size.

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