# Understanding when to count key comparisons

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?

Example:

 public class SortAndSearch{

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

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

• What do you mean by "put this into another method"? Can you give an example? – FrankW Sep 19 '14 at 14:13
• Yes, sorry. Here is an example. – 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.