I am having a hard time understanding what is O(1) space complexity. I understand that it means that the space required by the algorithm does not grow with the input or the size of the data on which we are using the algorithm. But what does it exactly mean?
If we use an algorithm on a linked list say 1->2->3->4, to traverse the list to reach "3" we declare a temporary pointer. And traverse the list until we reach 3. Does this mean we still have O(1) extra space? Or does it mean something completely different. I am sorry if this does not make sense at all. I am a bit confused.
n
, and it uses 10 kB for evenn
and 20 kB for oddn
. This function takesO(1)
space, but it certainly doesn't take a constant amount of space. This is not to be confused with constant space, which indicates a constant upper bound, not a constant amount.