Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Why is space complexity of the solution O(2^N)?

zachery.pang

Mar 15, 2024

Is space complexity of O(2^N) based on the number of results returned in the output?

Let me know if my interpretation is right:

The number of operators is linear in relation to the length of the expression

1 + 2 * 3 --> has 2 operators. Outputs: [7,9]

2 * 3 - 4 - 5 --> has 3 operators. Outputs: [8,-12,7,-7,-3]

2 * 3 - 4 - 5 + 6 --> has 4 operators. (My own example) Outputs: [20,-4,-24,20,0,13,1,-13,-9,14,-6,13,-1,3]

So given N operators (where length of expression is N + 1), the number of outputs is 2^N, and this is the space required to hold the values. Therefore, space complexity is O(2^N)

0

0

Comments
Comments

On this page