Exponential Complexity - O(2^n)

The runtime of the algorithm gets doubled after every addition in the input. (Reading time: 1 minute)

If an algorithm’s time complexity is O(2^n), its runtime is doubled after every addition to the input size. If 5 items took 30 seconds, 6 items would take 60 seconds.

In the following example, the value of an element is either 0 or 1. The amount of possibilities with 0 and 1 that this array could have, is 2^9 = 512.

Get hands-on with 1000+ tech skills courses.