Space complexity confusion

Question

I'm a bit confused about analyzing space complexity in general. I'm not sure the meaning of "extra space taken up by the algorithm". What counts as space of 1? In the example here

int findMin(int[] x) {
    int k = 0; int n = x.length;
    for (int i = 1; i < n; i++) {
        if (x[i] < x[k]) {
            k = i;
        }
    }
    return k;
}        

The space complexity is O(n), and I'm guessing it's due to an array size of n.

But for something like heapsort, it takes O(1). Wouldn't an in-place heapsort also need to have an array of size n(n is size of input)? Or are we assuming the input is already in an array? Why is heapsort's space complexity O(1)?

Thanks!

Answer 1

Heapsort requires only a constant amount of auxiliary storage, hence O(1). The space used by the input to be sorted is of course O(n).

Answer 2

Actually extra space corresponds to extra stack space that an algo uses i.e. other dan the input and generally it requires stack in recursive function calls , if recursion is present in algo than surely it will use stack to store contents until it get solved by termination condition.

The size of the stack will be O(height of the recursion tree).

Hope this is helpful!!