Explain the difference between O(1) vs O(n) space complexities

Technology CommunityCategory: Big-O NotationExplain the difference between O(1) vs O(n) space complexities
VietMX Staff asked 3 years ago

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 size n. That will happen if let’s say for some reason the algorithm needs to allocate ‘N’ pointers (or other variables) when traversing a list.