Meaning of the terms O(1) space and without using extra space
This is slightly confusing to me. What should be my approach of solving a given problem when the constraint is as follows:
1) Without using extra space: For e.g.: If I want to sort a given array, I have few ways of doing it. Bubble sort, which keeps on swapping ( just loops, no recursion). I believe this is said to be without using extra space. What is the case if I use a recursion to sort the elements. Is it the same as "without using extra space", or the stack used is counted in the Space complexity of the algorithm?
2) In O(1) space: What is the meaning of O(1) space? Does it mean constant space. Now if it is constant space then please comment on the following cases:
a) If I am swapping in bubble sort with the help of the third variable. Isn't it an extra space and it will not depend on the size of input so it is in constant space.
b) Moreover if I am using count sort being applied on natural numbers, where it doesn't really require the amount of space proportional to the total numbers, do we consider it to be in constant space O(1).
Please explain the difference if any. Thanks
Answer
According to Fortnow & Homer (2003),
The space complexity of the computation is [...] taken to be the amount of space used on the work tapes.
Sorting algorithm are all O(n) space in the least, since it needs the space to store all the inputs (no matter on memory or on disk). Therefore, even for bubble sort, the space complexity is still O(n).
However, sometimes, we are not interested in the overall space complexity (esp. in the case above), but we want to know the additional space used by the algorithm. For bubble sort, we can say that it uses constant amount of additional space.
Recursion is quite a special case where we have to consider stack. We are storing the state when we recurse, and we call the recursive function many times based on the input. As the number of recursion level depends on the input size, the space complexity must take into consideration the stack space usage.
I'm not sure if O(1) space algorithm is common or not, but Cycle Finding algorithm is one of such example. The algorithm by itself only use space for exactly 2 "pointers". Extra spaces used by the function whose cycle to be find should be counted separately.
In case of counting sort, the space complexity depends on the size of the input n (the count) and the maximum input value k. The 2 parameters are independent of each other, hence the space complexity is O(n + k). The additional space used can be defined as O(k).