Meaning of the terms O(1) space and without using extra space

Question

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 1

"No extra space" implies some amount of space, usually exactly n, is available via the input, and no more should be used, although in an interview I never care if the candidate uses O(1) extra. Honestly you would be hard-pressed in any modern language to avoid O(1) extra space for almost any trivial action you could take.

The stack counts when giving bounds on algorithms' space complexity.

O(1) means constant.

Counting sort uses at minimum O(k) space, where k is the largest possible key magnitude. Therefore, theoretically if we are talking about integers on a fixed number of bits, that is a constant. That is also why a radix sort is sometimes said to be a linear time sort.

Answer 2

O(1) : It is defined as the , in which input is bounded by a fixed constant number .we can compare this to when we have given integer range to be entered are between -10^5 to 10^5. So in breif we can say it signify bound on the values to be input .

O(n) : It is just opposite of the above when we have no condition on the input . As example , when we have to enter a string , then there is no condition on the length of string we entered

Answer 3

Before Answering the question, I just want to explain the meaning of extra constant space, For an algorithm to take constant extra space, the extra variables used to solve it should not change with the input size, for example, In bubble sort, the extra variable that we will use is the temp variable, it doesn't change with the size of the input array, we will always use the exact number of extra variables for any size.

Now coming to your first question: while dealing with recursion, the space complexity of the recursive algorithm is proportional to a maximum depth of recursion tree generated, so even if we are using a constant number of extra variables, the number of times these extra variable gets created will depend on the recursive call, which in turn depends on the size of the arr, which is not constant.

In count-sort, we are taking O(N+k) extra space to perform the sort, the N here will vary with inputs and so will K, so the extra space used will not be constant but O(n+k)

Hope this helps!!