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