Let’s consider a traversal algorithm for traversing a list.
O(1)
denotes constant space use: the algorithm allocates the same number of pointers irrespective to the list size. That will happen if we move (reuse) our pointer along the list.- In contrast,
O(n)
denotes linear space use: the algorithm space use grows together with respect to the input sizen
. That will happen if let’s say for some reason the algorithm needs to allocate ‘N’ pointers (or other variables) when traversing a list.