11 ms·

I always thought the Big-O notation was purely to compare one algorithm to another, not actually measure literal, real world performance. Trying to describe a

I always thought the Big-O notation was purely to compare one algorithm to another, not actually measure literal, real world performance. Trying to describe a hardware operation in Big-O notation then assert everyone should something other than O(1) for a memory access operation seems like a gross misunderstanding of its purpose.

fapjacks 10y ago
This right here is the most relevant response to the article.
TillE 10y ago
Specifically, Big-O describes the relative performance of an algorithm as the input grows. That's why constants are discarded, and that's why O(n^2) is probably fine if you only ever have very small data sets.
bzbarsky 10y ago
Big-O notation is there purely to compare one algorithm to another, yes. But in terms of what? Say you have two search algorithms. For a dataset of size N, Algorithm 1 does N memory reads and N data compares. Algorithm 2 does N * (log N) memory reads and log N data compares. These are not real algorithms, just illustrations. It's not uncommon in the analysis of such algorithms (both searching and sorting) to only consider the number of data compares and assume memory reads are completely free. So that would give you O(N) for algorithm 1 and O(log N) for algorithm 2. Analyses with more sophistication will note that a memory read is not in fact free, and will look at the number of "operations", whether those be memory reads or compares. In terms of the number of "operations", algorithm 1 is O(N) and algorithm 2 is O(N log N). These are both true statements about these algorithms: Algorithm 2 is O(log N) if you look at number of compares and O(N log N) if you look at number of "operations". Which of these characterizations is more relevant to you? Depends on whether memory reads are actually free in your setup. Anyway, the original article is arguing that for the comparison most people care about, wall clock time, even the more sophisticated version is wrong, because it assumes that the time needed per operation does not depend on N, so you can just count all the operations and not worry about their relative speed, because that's just a constant factor. If the time taken for a memory read _does_ depend on N, then you can't do that. For example, if you want to look at the algorithmic complexity of these algorithms in terms of clock cycles, and a compare is one clock cycle (might not be, depending on what your data is!) and a memory read if sqrt(N) clock cycles (due to caching effects), then the complexity of algorithm 2 will be O(N * sqrt N * log N), whereas algorithm 1 is O(N * sqrt N). Of course once you're caring about actual time very often constant factors start to matter too, and the whole idea of doing asymptotic analysis might break down. But it might not. It really depends on your exact problem and on the assumptions underlying the asymptotic analysis...
- dlubarov 10y ago
  > It's not uncommon in the analysis of such algorithms (both searching and sorting) to only consider the number of data compares and assume memory reads are completely free. Can you link to an example? That seems plainly wrong and I haven't seen an analysis which makes that assumption.
  - bzbarsky 10y ago
    https://en.wikipedia.org/wiki/Binary_search_algorithm#Performance https://en.wikipedia.org/wiki/Binary_search_algorithm#Perfor... is a simple example. It goes to great pains to talk about numbers of comparisons per iteration, but never once considers the number of memory accesses per iteration (which happens to be 1 or 2 depending on how you count things). In fact, most of the performance analysis of algorithms on Wikipedia that I've seen look like this. Similar for introductory algorithms textbooks, if I recall correctly (which I may not; it's been a while since I looked at one of those). Now in practice the number of memory accesses in an algorithm like this is typically O(1) in the number of comparisons so an implicit assumption that all your memory accesses are O(1) means just adding a constant factor to your overall complexity, so it's OK to just not worry about the whole thing. And counting "memory accesses" is complicated because whether something is a "memory access" or not is a bit tricky. For example, in the binary search case, do you need to "memory access" the value you're searching for before every compare, or can you assume it's stored in O(1) storage like a register? But all of this falls down if your memory accesses are not in fact O(1).
    - AstralStorm 10y ago
      There is a complimentary notation for additional memory use. Any engineer worth their salt actually specifies basic operations separately. This includes comparisons, fused or normal multiplies and additions, divisions of applicable, memory loads and writes. Even then you can get fooled due to locality.
mypalmike 10y ago
> purely to compare one algorithm to another, not actually measure literal, real world performance. Estimating real world performance is the whole point of Big-O notation. Trying to solve the traveling salesman problem on all the stars in the Milky Way is something your PC isn't going to do in your lifetime, for instance.
- GFK_of_xmaspast 10y ago
  If you ignore the nonEuclidean effects of general relativity, there are very good polynomial time approximation algorithms.

fapjacks 10y ago

This right here is the most relevant response to the article.

TillE 10y ago

Specifically, Big-O describes the relative performance of an algorithm as the input grows. That's why constants are discarded, and that's why O(n^2) is probably fine if you only ever have very small data sets.

bzbarsky 10y ago

Big-O notation is there purely to compare one algorithm to another, yes. But in terms of what? Say you have two search algorithms. For a dataset of size N, Algorithm 1 does N memory reads and N data compares. Algorithm 2 does N * (log N) memory reads and log N data compares. These are not real algorithms, just illustrations. It's not uncommon in the analysis of such algorithms (both searching and sorting) to only consider the number of data compares and assume memory reads are completely free. So that would give you O(N) for algorithm 1 and O(log N) for algorithm 2. Analyses with more sophistication will note that a memory read is not in fact free, and will look at the number of "operations", whether those be memory reads or compares. In terms of the number of "operations", algorithm 1 is O(N) and algorithm 2 is O(N log N). These are both true statements about these algorithms: Algorithm 2 is O(log N) if you look at number of compares and O(N log N) if you look at number of "operations". Which of these characterizations is more relevant to you? Depends on whether memory reads are actually free in your setup. Anyway, the original article is arguing that for the comparison most people care about, wall clock time, even the more sophisticated version is wrong, because it assumes that the time needed per operation does not depend on N, so you can just count all the operations and not worry about their relative speed, because that's just a constant factor. If the time taken for a memory read _does_ depend on N, then you can't do that. For example, if you want to look at the algorithmic complexity of these algorithms in terms of clock cycles, and a compare is one clock cycle (might not be, depending on what your data is!) and a memory read if sqrt(N) clock cycles (due to caching effects), then the complexity of algorithm 2 will be O(N * sqrt N * log N), whereas algorithm 1 is O(N * sqrt N). Of course once you're caring about actual time very often constant factors start to matter too, and the whole idea of doing asymptotic analysis might break down. But it might not. It really depends on your exact problem and on the assumptions underlying the asymptotic analysis...

dlubarov 10y ago
> It's not uncommon in the analysis of such algorithms (both searching and sorting) to only consider the number of data compares and assume memory reads are completely free. Can you link to an example? That seems plainly wrong and I haven't seen an analysis which makes that assumption.
- bzbarsky 10y ago
  https://en.wikipedia.org/wiki/Binary_search_algorithm#Performance https://en.wikipedia.org/wiki/Binary_search_algorithm#Perfor... is a simple example. It goes to great pains to talk about numbers of comparisons per iteration, but never once considers the number of memory accesses per iteration (which happens to be 1 or 2 depending on how you count things). In fact, most of the performance analysis of algorithms on Wikipedia that I've seen look like this. Similar for introductory algorithms textbooks, if I recall correctly (which I may not; it's been a while since I looked at one of those). Now in practice the number of memory accesses in an algorithm like this is typically O(1) in the number of comparisons so an implicit assumption that all your memory accesses are O(1) means just adding a constant factor to your overall complexity, so it's OK to just not worry about the whole thing. And counting "memory accesses" is complicated because whether something is a "memory access" or not is a bit tricky. For example, in the binary search case, do you need to "memory access" the value you're searching for before every compare, or can you assume it's stored in O(1) storage like a register? But all of this falls down if your memory accesses are not in fact O(1).
  - AstralStorm 10y ago
    There is a complimentary notation for additional memory use. Any engineer worth their salt actually specifies basic operations separately. This includes comparisons, fused or normal multiplies and additions, divisions of applicable, memory loads and writes. Even then you can get fooled due to locality.

mypalmike 10y ago

> purely to compare one algorithm to another, not actually measure literal, real world performance. Estimating real world performance is the whole point of Big-O notation. Trying to solve the traveling salesman problem on all the stars in the Milky Way is something your PC isn't going to do in your lifetime, for instance.

GFK_of_xmaspast 10y ago
If you ignore the nonEuclidean effects of general relativity, there are very good polynomial time approximation algorithms.