20
$\begingroup$

I think one reason a compare is regarded as quite costly is due to the historical research as remarked by Knuth, that it came from tennis match trying to find the second or third best tennis player correctly, assuming the tennis players are not a "rock paper scissors" situation (but has an "absolute 'combat' power").

If we have an array of size n being 1,000,000, we don't usually mind comparing 2,000,000 times to find the second largest number. With the tennis tournament, having a Player A match with Player B can be costly as it can take a whole afternoon.

With sorting or selection algorithms, for example, what if the number of comparisons can be O(n log n) or O(n), but then, other operations had to be O(n²) or O(n log n), then wouldn't the higher O() still override the number of comparisons? (Maybe it didn't happen yet, or else we would have a study case about this situation). So ultimately, shouldn't the number of atomic steps, instead of comparisons, measured by the order of growth as compared to n (O()) that determines the time complexity?

| cite | improve this question | |
$\endgroup$
  • 3
    $\begingroup$ You can do many different analysis. In our DB course we considered a model where you had "batch" read & writes that model loading a big node of a B-tree in memory, so when doing the complexity analysis of B-tree operations we not only looked at the number of comparisons etc but also at the number of node loads&writes. This can change how fast an algorithm is depending on how big the B-tree nodes are and how fast/slow you assume loading them takes. In fact B-trees are modeled to avoid having to recurse upwards to keep the tree short due to this, we want to minimize memory operations. $\endgroup$ – Bakuriu Mar 22 at 10:39
  • 1
    $\begingroup$ Case study: The C++ standard defines the complexity of some algorithms in terms of comparisons. This leads to the weird case where using binary_search over a sorted linked list is defined to have complexity $\mathcal{O}(\log_{2} N)$ (comparisons), whereas the actual complexity is going to be $\mathcal{O}(N)$ (number of pointer jumps).// This is just a case of model mismatch: In some theoretical (or early computer) models, the number of comparisons dominated. Nowadays, the comparison is quick, at least compared to memory lookup, so a different model fits better. $\endgroup$ – hoffmale Mar 23 at 22:01
22
$\begingroup$

Sure. But in practice that is rare: the sorting algorithms we usually use or analyze in practice do at most a constant number of other operations per comparison, so this isn't an issue for the sorting algorithms we actually care about. This means that measuring the number of comparisons or the number of steps taken gives you the same asymptotic running time.

Also, there are some situations where we use sorting algorithms where each comparison is much slower than the other operations. A comparison may be slower than the other operations, because conditional branches can be very slow on modern processors (each comparison may have a significant chance to cause pipeline flushes). And if you are sorting complex objects with a custom comparison function, then each comparison might take many instructions. So, in at least some cases, the number of comparisons might well dominate the over time it takes to sort the input.

Finally, there are certainly some cases we do take into account the time to perform other operations. It's most common to only count the number of comparisons, but by no means universal. In situations where the time taken for other operations is important, people do analyze the total running time.

Ultimately, asymptotic running time analysis is only a theoretical model. It is a simplified model that omits many considerations. Any such simplification will necessarily ignore many factors. As long as those factors are unimportant, this can be useful, as it helps you simplify the problem enough to analyze it and gain insight. But, as always, if one of those factors turns out to have a significant effect and you didn't include it in your model, then the model will yield misleading results -- this is true of all models, and is not limited to sorting or algorithmic analysis. Part of the art of modelling is identifying which factors dominate and which factors are second-order, so that you can choose a model that's only as complex as needed -- it is as simple as possible, so you can understand it better, but no simpler than that, so it still yields predictions that are reasonably representative of the real world.

| cite | improve this answer | |
$\endgroup$
  • 16
    $\begingroup$ A proper Unicode-based localised string comparison can be quite expensive. Especially if you add niceties like “999 sorts before 1000”. $\endgroup$ – gnasher729 Mar 22 at 7:44
  • $\begingroup$ Have there been any efforts at designing sorts which wouldn't have to do full key comparisons? If QuickSort had means of telling the comparison function function "until further notice, you may assume all items are going to have key values between those of item X and item Y", a comparison function could then check for a partial key match between those items, and then have future comparisons (until further notice) ignore the parts of the keys that matched in X and Y. If one is e.g. sorting a list of path names, I would think that could allow for some major improvements. $\endgroup$ – supercat Mar 22 at 21:43
  • $\begingroup$ "they flush the pipeline" is too pessimistic an oversimplification of conditional branches. That only happens if they mispredict. No "modern CPU" exists without some kind of branch prediction, at the very least static prediction. Comparison sorting is probably one of the worst cases for branch prediction rate, if you do it with branching instead of branchless min(x,y) max(x,y) comparators so yes this is a big problem, but I'd say "they flush the pipeline on mispredictions". $\endgroup$ – Peter Cordes Mar 23 at 1:07
  • $\begingroup$ That's still an oversimplification - CPUs that are actually modern (e.g. Intel since 2008's Nehalem) have fast recovery that snapshots the out-of-order state (including RAT) so branch recovery can start as soon as a mispredicted branch executes, not waiting to reach retirement. What exactly happens when a skylake CPU mispredicts a branch?. This can happen while earlier instruction are still in flight, e.g. overlapping a cache miss load with an independent branch mispredict. But modern CPUs have long pipelines and large OoO exec buffers so misses suck. $\endgroup$ – Peter Cordes Mar 23 at 1:11
  • $\begingroup$ @PeterCordes, thanks! Is my edit any better? In a good comparison-based sort, we'd expect that many of the comparison will be misses (probably trending to 50%, in a good sort on random data). $\endgroup$ – D.W.♦ Mar 23 at 1:48
9
$\begingroup$

If moving an item were n times more expensive than comparing, selection sort would suddenly be the most efficient algorithm. But if moving an item were expensive, we could sort an array of array indices, and then sort the original array in place with at most 1.5n moves. (That would actually be n/2 swaps; if a swap is cheaper than 3 moves then worst case is 4/3 n).

The number of comparisons cannot be lower than log n! for comparison based sorting.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The lower bound for the number of comparisons is lg(N!). That's usually described as O(NlgN), since it's the sum of the logs of values from 1 to N, and as N gets large, consecutive values of lgN get closer, and the sum behaves more and more like NlgN. There are definitely situations, though, where the actual number of comparisons required may be more or less than NlgN. As a simple example, for N=2, NlgN would be 2, but of course two items may be sorted with one comparison. For N=5, NlgN would be more than 10, but only 7 comparisons are required. $\endgroup$ – supercat Mar 22 at 21:53
  • 1
    $\begingroup$ The number of comparisons could be consistently three times N lg N and the algorithm would still be O(N lg N). That's how big-O works: it doesn't care about constant factors. I suppose you probably understand that, but let's not mislead others. (It's also true that big-O only really cares what happens for large N, so a few exceptions for small values of N wouldn't matter even if we had a particular constant factor in mind. I guess that's what you meant?) $\endgroup$ – David K Mar 22 at 23:55
  • $\begingroup$ @DavidK: Many sorting algorithms have a "lgN passes of N" structure, which might lead one to believe that NlgN, as opposed to O(NlgN) comparisons would be a lower bound. My intention was to allay any confusion caused by the fact that you wrote the bound as NlgN rather than O(NlgN). $\endgroup$ – supercat Mar 25 at 0:29
6
$\begingroup$

what if the number of comparisons can be O(n log n) or O(n), but then, other operations had to be O(n²) or O(n log n), then wouldn't the higher O() still override the number of comparisons?

Um, yeah. That's why, in such cases, we do use those other operations for the analysis. For example:

Binary insertion sort employs a binary search to determine the correct location to insert new elements, and therefore performs ⌈log2 n⌉ comparisons in the worst case, which is O(n log n). The algorithm as a whole still has a running time of O(n2) on average because of the series of swaps required for each insertion.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Big Oh analysis is looking at the asymptotic behavior of an algorithm. In these analyses, the thing which gets done "more" will always overshadow the thing which gets done less. As an example, consider an algorithm which does $O(n)$ disk operations at a cost of 1,000,000,000 units each, and $O(n^3)$ comparisons at a cost of 1 unit each. Obviously for small numbers of n, the disk operations will be the dominating part of the cost. However, as we get to large n, like 1,000,000,000, we see that we do 1,000,000,000 disk operations, for a total cost of 1,000,000,000,000,000,000 and we do 1,000,000,000,000,000,000,000,000,000 comparisons, meaning we spent literally a billion times more on the comparisons than on the disk reads, even though they are very light weight on their own.

This is not always the story we want. For many practical algorithms, we are not operating on such awful huge datasets where those small comparisons start to add up. In these cases we may do other things. In the case of "offline algorithms," which operate on databases on disks, we may measure the number of reads. Or we may even recognize that its cheaper to load a "page" of values all at once, so we try to measure how many pages have to get loaded.

This sort of study is useful, but it is not well captured in a simple Big Oh analysis. It typically has to account for what the hardware is good at, making the analysis more specialized. For example, there are cryptographic algorithms which are designed to be very inefficient on a GPU architeture, but very efficient on a CPU architecture.

My personal favorite of these is a particular disjoint set algorithm that came up when I was working on some fun threading problems. The complexity of it was one of those exotic things with O(log log N) terms showing up. But in the conclusion of the paper, they had to admit that their algorithm had some aspects which had such an ungodly large time constant that the less advanced algorithms were better for basically any dataset which fit onto a modern disk farm. Once your dataset started to move into the extabyte size scale, their algorithm started to earn its salt!

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

It seems like none of the other answers so far have mentioned a basic reason: There are many sorting algorithms whose total (asymptotic) time complexity is in fact bounded by the number of comparisons times the maximum time taken per comparison. Obviously that is why such sorting algorithms' cost should be measured by the number of comparisons, because they can be used to sort any input list from any set given a comparison function on that set.

Another more theoretical reason is that the information theoretic lower bound for sorting applies to the number of comparisons in the comparison model, so of course it makes most sense to measure the cost of a generic sorting algorithm in terms of the number of comparisons it takes.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

1. Because you can avoid the other operations being expensive.

Comparing integers is cheap. Comparing arbitrary elements of type T is typically as expensive as reading sizeof(T) bytes. Now, you might think "ok, but copying type-T elements is also expensive" - but we don't need to do that. We can just copy or move their indices in the input around and use those to lookup the original elements when comparing. Yet, we can't avoid the comparisons the same way.

Caveat: You can use hashing to avoid, typically, most costly comparisons.

2. It doesn't matter (except when it does)

You asked:

what if the number of comparisons can be O(n log n) or O(n), but then, other operations had to be O(n²) or O(n log n)

Well, the first option is a poor sorting algorithm anyway, and as for the second option - see @HeapOverflow's answer.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

The cost of comparison is more complex and depends on more than you imagine. Between each of the following is an order of magnitude cost increase.

  • Register
  • CPU Cache
  • RAM
  • Magnetic disk

Then there's the fact that your process does not run in isolation, but competes with other processes for system resources. Some of those processes will not be denied.

In the world of database engines, performance is all about mitigation of working set size. The smaller your working set, the less time you spend in the Slow Zone.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.