[mrami]

> If swaps are the only thing you are counting, selection sort is O(n).

And if you ignore the bottom half of the centaur, it's just a dude playing a flute. :)

"In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm." [1] We shouldn't be confusing people that actually want to learn about this stuff.

[1] https://en.wikipedia.org/wiki/Time_complexity

[thethirdone]

> And if you ignore the bottom half of the centaur, it's just a dude playing a flute. :)

That is an excellent phrase.

> We shouldn't be confusing people that actually want to learn about this stuff.

I definitely agree that Selection sort should definitely not be described as O(n) to beginners. I was just pointing out a subtly. In the strange case where memory writes are much more expensive than reads or comparisons, it is correct to say the Selection sort takes O(n) time.

[mrami]

I'm not sure what conditions you have in mind, but in the selection sort, the comparisons are O(n^2), and the assignments are O(n).

If comparisons are a fixed, non-zero cost, and assignments are a fixed, non-zero cost, then the comparisons in your selection sort will always overwhelm the assignments, and I can tell you at exactly which input size.

https://gist.github.com/mrami4/56d6e234f34787b8c5daf543a299a...

[ivanhoe]

> And if you ignore the bottom half of the centaur, it's just a dude playing a flute. :)

Good one, but you probably meant Satyr (or Faun as Romans called it)

[mrami]

Centaurs are multifaceted and live rich, complex inner lives.

https://commons.wikimedia.org/wiki/File:Achilleus_Lyra.jpg#/...