Grokking Algorithm Complexity and Big-O

0% completed

​

Exponential Time and Space: O(2ⁿ)

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:

.....

.....

.....

Like the course? Get enrolled and start learning!
STRYKER 316

STRYKER 316

· 2 years ago

It is mentioned that the depth of the recursion goes till 'N' levels.

But, then the space complexity is mentioned to be O(2^N) for some reason. It should be O(N), right?

The calls expand exponentially, but not every call is going to stack at the same time. There will be at max 'N' calls in the stack at a time.

Show 1 reply