This probably is a very basic question for some of you, but please bear with me.

Information I read: Space complexity is not the same as auxiliary memory. It includes auxillart memory and the memory required to store input values.

#include<iostream>

int linearSearch(int array[], int length, int value){
    int location = -1;
    for(int i = 0; i < length; i  ){
        if(array[i] == value){
            location = i;
            break;
        }
    }
    
    return location;
}

int main(){
    
    int value = 40;
    
    int data[] = {0,1,2,3,4,-5,6,7,8,9,-10};
    int length = sizeof(data)/sizeof(int);
    
    int location = linearSearch(data, length, value);
    
    if(location == -1){
        std::cout << "Element not found!\n";
    }
    else{
        std::cout << "Element present at : " << location << std::endl;
    }
}

Considering the definition and the code above, since the size of array increases with the input, shouldn't the space complexity be O(n)? Of course the auxiliary space required is constant but what about the space complexity?

CodePudding user response：

What does O(1) space mean? It means that the amount of memory your algorithm consumes doesn't depend on the input. The algorithm should use the same amount of memory for all inputs.

So, the linear search only need one element need(that is the variable you used to compare with all the elements in the array), so no matter how big or small your array is, the algorithm only consumes the same amount of memory for all input, and thus is space complexity is O(1)

CodePudding user response：

It includes auxillart memory and the memory required to store input values.

This sentence is correct. However, you seem to be thinking that your linear search implementation stores the input. If that were correct, it would indeed have an O(n) space complexity. But it just stores a reference to the input.

Note that in C/C with the syntax you are using you do not copy the array when calling linearSearch. Think of the int array[] parameter as a pointer. int* array would work the same way (there are some very subtile differences, but for the scope of this question these two syntaxes can be considered 100% equivalent).

Knowing that, it should be obvious that the space complexity of linearSearch is indeed O(1) because it only ever consumes space for 1 pointer (array) and 4 integers (length, value, location, i).