66

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.

coder123
  • 841
  • 1
  • 7
  • 19
  • 8
    o(1) space complexity means that the amount of memory that you use is constant and does not depends on the data that it is processing, more information [here](http://btechsmartclass.com/DS/U1_T3.html) – Rodrigo Gonzalez Apr 06 '17 at 16:37
  • 1
    @RodrigoGonzalez that's not strictly true. First of all you wrote little-o, which is not the same as big-O. Assuming you meant Big-O: Suppose you have a function that takes a single integer input `n`, and it uses 10 kB for even `n` and 20 kB for odd `n`. This function takes `O(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*. – ubadub Oct 25 '18 at 18:18

3 Answers3

105

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.

lolski
  • 16,231
  • 7
  • 34
  • 49
Ajay Kumar
  • 1,253
  • 1
  • 11
  • 17
  • What does it to do with temporary pointers and non-temporary pointers?Thanks in advance for answering. – LED Fantom May 01 '18 at 21:30
  • 2
    Sorry, that word was not relevant to the answer, hence removed it :) When we are talking about space complexity, we only care about the storage used during the program execution. – Ajay Kumar May 03 '18 at 05:33
  • 6
    For a better understanding of what big-O actually is: If you have 1000 pointers, you can also say it's O(1000). This is the same as O(1) because big-O [doesn't care](https://stackoverflow.com/questions/22188851/why-is-the-constant-always-dropped-from-big-o-analysis) about [constant factors](https://stackoverflow.com/questions/22614585/what-is-constant-factors-and-low-order-term-in-algorithms). O(1) is conventionally used because it's the simplest form. – Bernhard Barker Jun 23 '20 at 04:35
  • Is it fair to say that any pure algorithm which returns a copy of the data must be at least O(N) while algorithms which mutate data (in-place) could be O(1)? – MattCochrane Feb 14 '21 at 04:57
  • what if the number of pointers change based on input but the max number of pointers can be only upto 100. Is this treated as O(1) or O(N)? – Sai Sunder Jun 29 '21 at 06:12
-1

It is just the amount of memory used by a program. the amount of computer memory that is the main memory required by the algorithm to complete its execution with respect to the input size.

Space Complexity(s(P)) of an algorithm is the total space taken by the algorithm to complete its execution with respect to the input size. It includes both Constant space and Auxiliary space.

S(P) = Constant space + Auxiliary space

Constant space is the one that is fixed for that algorithm, generally equals to space used by input and local variables. Auxiliary Space is the extra/temporary space used by an algorithm.

0xh3xa
  • 4,801
  • 2
  • 14
  • 28
Suresh P
  • 1
-3

Let's say I create some data structure with a fixed size, and no matter what I do to the data structure, it will always have the same fixed size. Operations performed on this data structure are therefore O(1).

An example, let's say I have an array of fixed size 100. Any operation I do, whether that is reading from the array or updating an element, that operation will be O(1) on the array. The array's size (and thus the amount of memory it's using) is not changing.

Another example, let's say I have a LinkedList to which I add elements to it. Every time I add an element to the LinkedList, that is a O(N) operation to the list because I am growing the amount of memory required to hold all of it's elements together.

Hope this helps!

Matthew S
  • 343
  • 3
  • 11
  • This is a very poor example. While a C array does not change size whenoperations are applied to its members, that is not true of other languages – symcbean Apr 19 '17 at 11:49
  • I understand, this particular example applies to C language and may not apply to the implementations of other languages. I'll add an appendix to my explanation once I have time. Thanks for the input @symcbean – Matthew S Apr 19 '17 at 16:08
  • 4
    This is not what `O(1)` means. A `O(1)` function doesn't need to use a *fixed* size for all inputs, it just has to have a constant upper bound (on space) for all inputs. For example, suppose you have a function that takes a single integer input `n`, and it uses 10 kB for even `n` and 20 kB for odd `n`. This function takes `O(1)` space, but it certainly doesn't use a *fixed size*. However, the *upper bound is fixed*, at 20 kB. – ubadub Oct 25 '18 at 18:21
  • Note to reviewers in the VLQ queue: [Wrong answers are not Very Low Quality](https://meta.stackoverflow.com/questions/345023/are-blatantly-wrong-answers-very-low-quality). Please vote "Looks OK" on this. – EJoshuaS - Stand with Ukraine May 17 '22 at 16:13
  • Oh man, I had a good laugh looking back at this answer I gave and then looking at the thread you posted @EJoshuaS-StandwithUkraine. I agree this is one of those 'how NOT to think about O(1)' and is pretty valuable in itself, although it is blatantly wrong. – Matthew S May 25 '22 at 22:12