0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Maybe look at this answer cs.stackexchange.com/questions/1354/… $\endgroup$ – Louis Apr 2 '14 at 14:58
  • 2
    $\begingroup$ This is only a simplifcation for beginners and lazy people. There are plenty of analyses of other operations, too. It just so happens that comparisons are often the dominant operation in sorting (for comparison sorts!) so for the sake of "Big-Oh" analysis, it's quite enough to investigate them. $\endgroup$ – Raphael Apr 2 '14 at 15:16
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ i am sorry but i didn't understand the second reason's relevance to question $\endgroup$ – Bhushan Apr 2 '14 at 13:58
  • $\begingroup$ Well, we like to compare the algorithm to other algorithms and the comparisons provide a notion of optimality. $\endgroup$ – frafl Apr 2 '14 at 14:01
1
$\begingroup$
...while calculating time complexity and operations such as swap are ignored

You are wrong. All the operations are taken into account when calculating time complexity. But as loops are dominant compared to other operations, we ignore other operations and only consider dominant operations(Because for large input value, cost of all other operations are much smaller than the dominant operations) .

As an example with selection sort: When you consider all statement costs into account then you get a function $f(n)=an^2+bn+c$ ($a$,$b$ and $c$ are constants and depend on machine architecture). Here dominant term is $an^2$.So we can say Time complexity of selection sort $O(an^2)$.We also ignore leading terms coefficient $a$ ,as $a$ does not change the rate of growth.

I suggest you to study some standard algorithm textbook to understand it properly.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.