Does Big O Measure Memory Requirments Or Just Speed?

Question

I often here people talk about Big O which measures algorithms against each other

Does this measure clock cycles or space requirements.

If people want to contrast algorithms based on memory usage what measure would they use

Answer 1

Typically it's the number of operations, which translates to speed. Usually, algorithms differ more in speed than in memory usage. However, you will see the O() notation used for memory use, when appropriate.

Answer 2

Short answer : you have 'Big O in space" and "Big O in time".

Long answer: Big O is just a notation, you can use it in whatever context you want.

Answer 3

Big O is just a mathematical tool that can be used to describe any function. Usually people use it to describe speed, but it can just as well be used to describe memory usage.

Also, when we use Big O for time, we're usually not talking directly about clock cycles. Instead, we count "basic operations" (that are implicitly assumed to take a constant number of cycles).

Answer 4

"Big O" is just about computational complexity, so just speed. Memory usage can depend on how the algorithm is implemented, for example classic quick sort in C is implemented to work in-place so memory requirements are minimal. The standard implementation of quick sort in a functional language does not work in-place and thus has double the memory requirements.

Answer 5

If someone says "This algorithm runs in O(n) time", he's talking about speed. If someone says "This algorithm runs in O(n) space", he's talking about memory.

If he just says "This algorithm is O(n)", he's usually talking about speed (though if he says it during a discussion about memory, he's probably talking about memory).

If you're not sure which one someone's talking about, ask him.

Answer 6

Big O is really just a measure of the growth of complexity based on growth of input. Two algorithms with are both O(n) may execute in vastly different times but their grown is linear with relation to the growth of the input.

Answer 7

While normally algorithms compete on time, then I would normally assume that any O statement was time. However, it's perfectly valid to also compare space. O can be used for any measurement- we just normally use speed because it's normally the most important.

Answer 8

Big-O can be used to describe the relationship between any two quantities. Although it is generally only used in computer science, the concept may also be applicable in other fields like physics. For example, the amount of power that must be put into an antenna of a given size to yield a unit-strength signal at some distance is O(d^2), regardless of the antenna shape. If the size of the antenna is large relative to the distance, the increase in strength required may be linear or even sub-linear rather than quadratic, but as the distance gets larger, the quadratic term will dominate.

Answer 9

Big O and others are used to measure the growth of something.

When someone says that something is O(N), then that thing grows no faster than linear rate. If something is Ω(N^2), then that thing grows no slower than quadratic rate. When something is Θ(2^N), then that thing grows at an exponential rate.

What that thing is can be the time requirement for an algorithm. It can also be the space i.e. memory requirement for an algorithm. It can also be pretty much anything, related to neither space nor time.

For example, some massively parallel algorithms often measure the scalability in the number of processors that it can run on. A particular algorithm may run on O(N) processors in O(N^2) time. Another algorithm may run on O(N^2) processors in O(N) time.

Related questions

• Big-oh vs big-theta

See also

• Wikipedia/Big O Notation