What does this mean: O(n) steps and O(1) space?
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.
Answer
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.