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.
+9
A:
O(1) space means that the (worst-case) memory required by the algorithm is constant, i.e. does not depend on the size of the input.
O(n) space means that the (worst-case) memory required has the same order of magnitude as the input.
Edit: Adding two examples:
- An bubble-sort requires O(1) space.
- A merge-sort requires O(n) space.
3lectrologos
2010-02-08 01:17:00
so then basically a recursive call would usually be the O(n) space and an iterative process would be O(1) since you're not waiting for a recursive call(s) to finish?
Devoted
2010-02-08 01:18:52
Added two common examples. Well, you can't really find general rules about recursive vs iterative algorithm complexities (but it's probably hard -if not impossible- for a recursive algorithm to have O(1) space complexity).
3lectrologos
2010-02-08 01:24:34
if your recursive call used new variables every time it was called then yes it would be O(n) space. If your iterative process instantiated new variables in a loop without releasing then it too would O(n). It all depends on how you design and code the algorithm.
Nikhil
2010-02-08 01:25:58
@Nikhil: Actually, recursive calls always consume space for activation records, so even if you don't have local variables, complexity wouldn't be O(1).
3lectrologos
2010-02-08 01:30:28
@3lectrologos: unless, of course, you're using tail recursion. If you have a tail-recursive function with no local variables, then it'll be O(1) space.
DK
2010-02-08 02:36:55
+2
A:
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.
mbarnett
2010-02-08 01:18:00