Take the worse case for insertion sort where there is an array of n decreasing elements. The total time spent comparing all element, from left to right, is:
1 + 2 + ... + (n - 2) + (n - 1)
Also considered in calculating the time complexity is swapping those elements, which is also:
1 + 2 + ... + (n - 2) + (n - 1)
Ultimately, we arrive at O(n^2).
Take another algorithm like binary search; the act of finding a midpoint, and then after comparing to that midpoint, reassigning your midpoint to high or low during each division of the list in half doesn't count at all towards the time complexity. Only the act of comparing the midpoint to the target value. So why does swapping in classic sorting algorithms, which are three assignment statements, impact the time complexity but the assignments of the midpoint in binary search do not?
UPDATE
As Taylor Edmiston pointed out,
n the binary sort, lookup is cheaper in a tree structure vs insertion sort where the data structure is an array/list. The pathological case for the insertion sort is every element having to be swapped past every single other element already in the list.
But isn't "swapping" really just three variable assignments?
if (a[i] > a[j])
x = a[i];
a[i] = a[j];
a[j] = x;
How are those three assignments any more or less of a dominating factor than the following that you see in a general binary search algorithm?
while(low < high)
mid = (low + high) / 2; // assignment 1
if (data[mid] == target)
return true;
if (data[mid] < testValue)
low = mid + 1; // assignment 2_a
else
high = mid; // assignment 2_b
They do !
In insertion sort, you perform O(n²) comparisons and O(n²) assignments, and the total is still O(n²).
In binary search, you perform O(Log n) comparisons and O(Log n) assignments and the total is still O(Log n).
But it is common practice, when you know that some operation is performed in proportion of another (i.e. in binary search, one assignment per comparison), to only count one type of operation.
By the way, think that there are other operations that were not accounted for, such as array dereferences or loop statements. Using the big-Oh notation, we don't care, as long as the numbers of operations remain proportional (or of a lower order of magnitude).
Additional example:
One can implement insertion sort with a binary search followed by swaps.
In such a version, you would perform approximately
Log 1 + Log 2 + Log 3 + Log n-1 comparisons, which is O(n Log n),
and still O(n²) swaps. Globally, the algorithm behavior is O(n²).
In the complexity analysis, you could dispense yourself with counting the comparisons, as they enter into play with a lower order of magnitude, and only care about the assignments. Provided this imbalance is established !