Timeline for Quicksort Time Complexity
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 9, 2020 at 22:07 | comment | added | gnasher729 | Just saying: The first problem is not that easily fixed. If you want to pick something other than the first element as the pivot, you'll have to think very, very hard about the last swap. I hope everyone reading the code takes a very, very hard look at the last two lines. I'd want very good comments in the code explaining why they are correct, otherwise I'd find the code unacceptable. | |
| Jun 9, 2020 at 21:54 | comment | added | gnasher729 | Just saying: This implementation has two fatal flaws: One, it will result in a total of O (n^2) comparisons if an array is already sorted; this is very easily fixed. Two, it will result in O (n^2) comparisons if all array elements are equal, which is much harder to fix. | |
| S Jun 9, 2020 at 20:38 | history | suggested | Glorfindel | CC BY-SA 4.0 | thanks removed as per https://meta.stackexchange.com/q/2950/295232 |
| Jun 9, 2020 at 19:57 | review | Suggested edits | |||
| S Jun 9, 2020 at 20:38 | |||||
| Jun 9, 2020 at 19:14 | comment | added | Nick Nemtcev | @YuvalFilmus, yes, I am counting the comparisons. For reference, I am following the notes provided on Emory University's page if they are of any use: mathcs.emory.edu/~cheung/Courses/171/Syllabus/7-Sort/… (towards the bottom) | |
| Jun 9, 2020 at 19:00 | answer | added | nir shahar | timeline score: 1 | |
| Jun 9, 2020 at 18:59 | comment | added | Yuval Filmus | Moreover, the difference between $n-1$, $n$ and $n+1$ is usually highly unimportant when determining the asymptotic time complexity of a function. | |
| Jun 9, 2020 at 18:58 | comment | added | Yuval Filmus | I have never seen a definition of "unit of work", and that's definitely not a standard concept. Are you counting comparisons by any chance? | |
| Jun 9, 2020 at 18:50 | review | First posts | |||
| Jun 9, 2020 at 19:57 | |||||
| Jun 9, 2020 at 18:47 | history | asked | Nick Nemtcev | CC BY-SA 4.0 |