Menu
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.
551
O(1) – constant complexity – takes the same amount of space regardless of the input size. O(log n) – logarithmic complexity – takes space proportional to the log of the input size. O(n) – linear complexity – takes space directly proportional to the input size.
O(1) — Constant Time Constant time algorithms will always take same amount of time to be executed. The execution time of these algorithm is independent of the size of the input. A good example of O(1) time is accessing a value with an array index. Other examples include: push() and pop() operations on an array.
In an iterative implementation of Binary Search, the space complexity will be O(1). This is because we need two variable to keep track of the range of elements that are to be checked. No other data is needed. In a recursive implementation of Binary Search, the space complexity will be O(logN).
Space complexity of O(n) means that for each input element there may be up to a fixed number of k bytes allocated, i.e. the amount of memory needed to run the algorithm grows no faster than linearly at k*N.
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.
155
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
