New answers tagged

2

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


2

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


1

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


0

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


6

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


9

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


22

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


Top 50 recent answers are included