Hands-On High Performance with Go

O(2n) – exponential time

An exponential algorithm grows exponentially when data is added to the input set. These are usually used when there isn't an inclination of the input dataset and you must try every possible composite of the input set.

Some examples of exponential time are as follows:

• Poor recursion implementation of the Fibonacci sequence
• Towers of Hanoi
• Traveling salesman problem

Normalized timings for exponential time can be found in the following table:

Number of items in the dataset	Resulting computation time
10	1,024 seconds
100	1.267 * 1030 seconds
1,000	1.07 * 10301 seconds

As the number of items in the dataset grows, the resulting computation time grows exponentially.

Exponential time algorithms ...