What is O(1) space complexity?

To answer your question, if you have a traversal algorithm for traversing the list which allocate a single pointer to do so, the traversal algorithms is considered to be of O(1) space complexity. Additionally, let’s say that traversal algorithm needs not 1 but 1000 pointers, the space complexity is still considered to be O(1).

However, if let’s say for some reason the algorithm needs to allocate ‘N’ pointers when traversing a list of size N, i.e., it needs to allocate 3 pointers for traversing a list of 3 elements, 10 pointers for a list of 10 elements, 1000 pointers for a list of 1000 elements and so on, then the algorithm is considered to have a space complexity of O(N). This is true even when ‘N’ is very small, eg., N=1.

To summarise the two examples above, O(1) denotes constant space use: the algorithm allocates the same number of pointers irrespective to the list size. In contrast, O(N) denotes linear space use: the algorithm space use grows together with respect to the input size.

Leave a Comment