Runtime $\mathcal{O}(2^n)$

As we increase our input size by 1 we are going to double the output.

from stopwatch import Stopwatch

# Recursive function that will return O(2^N)
def exponential_run_time(N):
    if N == 0:
        return 1
    total_operations = 0
    total_operations += exponential_run_time(N - 1)
    total_operations += exponential_run_time(N - 1)
    return total_operations

if __name__ == '__main__':
    input_sizes = [12, 13, 14, 15, 16, 17]
    for input_size in input_sizes:
        timer = Stopwatch()
        total_operations = exponential_run_time(input_size)
        print(input_size, total_operations, timer.elapsed_time())

As we increase our input size by 1 the total number of operations double unless the time it takes to complete this operation also doubles.

2^30 = 1 billion

If you try to do input size of 60, billion squared runtime. Anything in the range of 100 is not feasible for an exponential run time.

We may run into problems that have exponential solutions and as creative programmers we want to find solutions that are quadratic or linear. Pretty much anything is better than exponential.


19:50 => 22:31