Space Complexity of an initialised pointer data structure

Question

I have got a question.

In terms of theoretical computer science, when we analyse an algorithm, if an algorithm initialises a new data structure, then we consider that data structure as part of space complexity.

Now I am not too sure about this part then.

Let's say I have got an array of int and I would like to map them by using a map of int pointers. Such as

std::map<int*,int*> mymap;
for (int i = 1; i < arraySize; i++) {
   mymap[&arr[i-1]]=&arr[i];
}

If this algorithm was not using pointers, then we could clearly state that it is initialising a map with size of n, hence space complexity is O(n), however for this case, where we are using pointers, what would be the space complexity of this algorithm?

Answer 1

The space complexity of a single pointer is the same as that of any other primitive - i.e. O(1).

std::map<K,V> is implemented as a tree of N nodes. Its space complexity is O(N*space-complexity-of-one-node), so the total space complexity in your case is O(N).

Note that the big-O notation factors out the constant multiplier: although the big-O space complexity of an std::map<Ptr1,Ptr2> and std::vector<Ptr1> is the same, the multiplier for the map is higher, because tree construction imposes its overhead for storing tree nodes and connections among them.