[Solved]: Why don't we calculate swaps and other steps except comparison for finding time complexity of a sorting algorithm?

Problem Detail: 

I was learning some basic sorting techniques with their complexity. However I cannot understand why only the number of comparisons are taken into account while calculating time complexity and operations such as swap are ignored. Link to selection sort analysis. Please help me understand.

Asked By : Bhushan

Answered By : frafl

There are 2 major reasons:

1. For most algorithms the number of other operations can be bounded by a multiple of the number of comparisons (i.e. runtime in $\mathcal{O}(\#comparisons)$). This is because e.g. a swap does not occur without a prior comparison requiring this swap (depends on algorithm).

2. Using comparisons you can prove an $\mathcal{O}(n \log n)$ lower bound for any comparison based sorting algorithm on $n$ elements.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/23339