Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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.

like image 278
Devoted Avatar asked Feb 08 '10 01:02

Devoted


1 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.
like image 184
3lectrologos Avatar answered Sep 23 '22 09:09

3lectrologos