Hi,
There’s one thing I’ve been finding a little confusing, which is how you define “Space Complexity” here. I’ve studied in different sources that Space completity = Input size + Auxiliary Space. So, if you have an input array, your Space Complexity will be already O(n) just because of given array of size N. But it seems that you are considering only the extra space needed to allocate, which is the Auxiliary Space. Should I read your “Space Complexity” as “Auxiliary Space Complexity”? Or did I misunderstand everything?
Thank you!
Hi @Hector_A ,
Thank you for reaching out to the Educative Team!
The space complexity of an algorithm = Input size + Auxiliary Space, as you have already mentioned. However, when we need to compare the algorithm’s working with another algorithm, using only Auxiliary Space is a better criterion. Here, in this lesson, the author is comparing different solutions to the problem in order to find the best solution. That is why, in this lesson, Space Complexity = Auxiliary Space.
Hope you have gotten the answer to your question. In case of any confusion, feel free to reply in the thread. Have fun learning the Educative way!