educative.io

Why is the space complexity O(N) for this?

Courses
,
#1

I’m confused regarding how the space complexity came out to be O(N) when we are not using any auxiliary space to store the recursion stack and instead we are only passing in the same sequence array for each recursion and using sequenceIndex variable to keep track?

Type your question above this line.

Course: https://www.educative.io/collection/5668639101419520/5671464854355968
Lesson: https://www.educative.io/collection/page/5668639101419520/5671464854355968/5750943224168448

#2

Hi @Shantanu_Singh

Although we are not explicitly allocating any space, however, as recursion is taking place, each call to the function is pushed onto the stack which uses space in memory. In the worst case, the space complexity will be O(N), in the case that each node in the tree has exactly one child.

Hope this helped!

1 Like
#3

Got it @Hafsa_Kamran

Thanks for the response.

1 Like