0
$\begingroup$

As per the example given in this MIT OCW link URL https://ocw.mit.edu/courses/civil-and-environmental-engineering/1-124j-foundations-of-software-engineering-fall-2000/lecture-notes/sorting/

Why selection sort requires $O(N)$ time since the number of exchanges is at most N. Pls give example algorithm that prove this fact. Below is excerpt taken from same MIT OCW URL for reference

Selection sort is easy to implement; there is little that can go wrong with it. However, the method requires $O(N^2)$ comparisons and so it should only be used on small files. There is an important exception to this rule. When sorting files with large records and small keys, the cost of exchanging records controls the running time. In such cases, selection sort requires $O(N)$ time since the number of exchanges is at most $N$.

$\endgroup$
  • $\begingroup$ The example algorithm is selection sort. $\endgroup$ – Yuval Filmus Nov 9 '17 at 15:12
3
$\begingroup$

It is simpler and more correct to say: selection sort requires $O(n)$ exchanges (and this is optimal in the worst case).

That doesn't imply $O(n)$ time, unless the other operations take negligible time. But from a theoretical standpoint, $O(n^2)$ is never negligible compared to $O(n)$.

In practice if a comparisons and related overhead takes $s$ seconds and an exchange and related overhead takes $e$ seconds, the total time will be

$$\frac{sn^2}2+cn=\left(\frac{sn}2+c\right)n.$$

This can be considered a linear behavior as long as $sn\ll c$. That could be true if the records are stored on a slow disk while the keys are cached in RAM.


This course plays a dangerous game with the Big-$O$ notation.

$\endgroup$
0
$\begingroup$

Suppose that the cost for comparing two keys is $A$ and that the cost for exchanging two records is $B$. Then the running time of selection sort is $$ O(An^2 + Bn). $$ If $A$ is much smaller than $B$ (by a factor of $\Omega(n)$), then the second term is dominant.

$\endgroup$
  • $\begingroup$ @YvesDaoust You are assuming that $A,B$ are constants, but they could depend on $n$. For example, in some application they key could have logarithmic size while the record could have linear size. $\endgroup$ – Yuval Filmus Nov 9 '17 at 18:08
  • $\begingroup$ You must write $A(n),B(n)$. $\endgroup$ – Yves Daoust Nov 10 '17 at 8:03
  • $\begingroup$ Who said so? Do you also forbid writing $O(n+m)$? $\endgroup$ – Yuval Filmus Nov 10 '17 at 10:40
  • $\begingroup$ Ok, your choice to be bad faith. $\endgroup$ – Yves Daoust Nov 10 '17 at 10:46

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.