3 ms·

> 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 com

> 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.

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.