Exponential Time and Space: O(2ⁿ)

Grokking Algorithm Complexity and Big-O

Ask Author

Back to course home

0% completed

Vote For New Content

Exponential Time and Space: O(2ⁿ)

Table of Contents

Contents are not accessible

Exponential Time Complexity $O(2^n)$ and Exponential Space Complexity $O(2^n)$ both describe algorithms where the time and memory requirements double with each increase in input size. This growth is extremely fast, making these algorithms impractical for large inputs. Both exponential time and space complexities commonly appear in recursive algorithms that explore all possible combinations, such as the naive recursive approach to calculate the Fibonacci sequence.

Key Characteristics

In an algorithm with $O(2^n)$ time and space complexity:

Time Complexity: The number of operations doubles with each additional element in the input.
Space Complexity: The memory usage also doubles, as each recursive call requires additional stack frames.

Code Example: Find All Subsets of a Given List

Below is a Java example that finds all subsets of a given list using recursion:

Python3

. . . .

Explanation:
- The main method starts the recursive process.
- The helper function findSubsets goes through each element in the list.
- At every call, the function makes two recursive calls: one that skips the current element and one that adds it.
- When the index reaches the size of the list, the current list is added to the results.

Complexity Analysis

Time Complexity

To estimate the time taken, we can use a recurrence relation.

Step 1: Define the Recurrence Relation

Let T(n) be the time to compute all subsets of a list with n elements.
At each step, the function makes two recursive calls.

T(n) = 2 * T(n - 1) + O(1)

Step 2: Expand the Recurrence Relation

When we expand T(n), we see that the number of calls doubles at each step.
Thus, T(n) is proportional to $2^n$ .
The time complexity is $O(2^n)$ .

Space Complexity

The space needed grows quickly because we store all the subsets.

Recursive Call Stack:
- The deepest the recursion goes is n, but this is not the main use of space.
Storage for All Subsets:
- Since there are $2^n$ subsets, and each is stored in memory, the space required grows with $2^n$ .

The space complexity is $O(2^n)$ .

Why Exponential Complexity Is Infeasible for Large Inputs

Exponential growth means that even a small rise in n causes a large increase in the number of subsets. For example:

If n = 10, there are 2^10 = 1024 subsets.
If n = 20, there are 2^20 = 1,048,576 subsets.

This quick rise makes the algorithm impractical for lists with many elements.

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible