Does Big O Measure Memory Requirments Or Just Spee

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

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 2

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

Answer 3

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 4

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 5

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 6

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.