Timeline for What is the first interesting theorem in (insert subject here)?
Current License: CC BY-SA 2.5
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 11, 2009 at 10:09 | comment | added | Konrad Swanepoel | Yijie Han dx.doi.org/10.1016/j.jalgor.2003.09.001 has an algorithm for sorting natural numbers that takes time O(n log log n). So it really depends on the class of sorting algorithms. Any comparison sort needs at least $\log_2 n! > c n \log n$ comparisons. | |
| Oct 24, 2009 at 20:46 | comment | added | Ilya Nikokoshev | Well, it's simply about the way you define your problem; other sorts have input defined in a different way. "Hence, radix sort does not really beat O(n log n) time, it only appears to do so because the range of keys is implicitly limited by the size of k." (from wikipedia) | |
| Oct 24, 2009 at 20:35 | comment | added | Steven Sam | That is only true for comparison-based sorting algorithms. There are non comparison-based sorting algorithms if your data consists of numbers or alphabets, or things like that. For example, radix sort: en.wikipedia.org/wiki/Radix_sort | |
| Oct 24, 2009 at 20:21 | comment | added | Ilya Nikokoshev |
Comparison as in bubble sort (nn) or as in some other sort? I mean *any sorting algorithm requires asymptotically at least C * n * log n.
|
|
| Oct 24, 2009 at 20:16 | comment | added | Steven Sam | Nitpick: Comparison based sort is \Omega(n*log n). | |
| Oct 24, 2009 at 20:09 | history | answered | Ilya Nikokoshev | CC BY-SA 2.5 |