What does O(1) space mean? I understand that O(n) steps is like the order of magnitude of calculations an algorithm/program makes, but don't know what the O(n) space is.
2 Answers
O(1) space means that the memory required by the algorithm is constant, i.e. does not depend on the size of the input.
O(n) space means that the memory required by the algorithm has (in the worst case) the same order of magnitude as the size of the input.
Edit: Adding two examples:
- Bubblesort requires O(1) space.
- Mergesort requires O(n) space.
Essentially "O(n) steps and O(1) space" would mean that the number of steps the algoritm performs scale linearly (O(n)) with the number of items, but the amount of memory it takes is constant.
Related