I understand that for something like Linear search, this would be the key comparison:

 if(itemToFind == a[i])
    return i;

If I put this method into another method, say a Sorting method, do I still count the linear key comparison plus the sorting key comparison? Or do I only care about the sorting key comparison?


 public class SortAndSearch{

 void QuickSortAndSearch(A, p, r){
         q = Partition(A,p,r)

      if(itemToFind == a[i])
    return i;
  • $\begingroup$ What do you mean by "put this into another method"? Can you give an example? $\endgroup$ – FrankW Sep 19 '14 at 14:13
  • $\begingroup$ Yes, sorry. Here is an example. $\endgroup$ – AmbitiousCoder Sep 19 '14 at 14:19

I'll answer some other question first: Why do we count key comparisons?

When analysing the runtime of an algorithm it can be tedious to count all the operations (even more so, if we notice they don't all take the same time). So it is convenient to identify those operations that dominate the runtime and only analyse those.

In the case of searching the dominant operation are key comparisons, in the case of sorting, they are key comparisons and swaps. Furthermore, most sorting algorithms will only swap elements that they have compared just prior. Thus the number of comparisons gives an upper bound for the number of swaps as well. So we can get away with counting the number of comparisons in order to get an idea of how the (worst-case) runtime of an algorithm behaves.

Now to your actual question:

If key comparisons are the dominant operation, e.g. in an algorithm that combines sorting and searching, then it is useful to count all key comparisons, if we want to get an idea of the runtime.

If, on the other hand the key comparisons are dominated by some other operation, then it might make more sense to count those other operations and not count any key comparisons.

Or the key comparisons are one of several operations, neither of which dominates the others, then we count all of those. Or in one part of the program key comparisons are dominant, while in another part they are not. Or ...

| cite | improve this answer | |

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.