Timeline for Computational complexity of calculating mean vs median?
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 23, 2019 at 21:03 | answer | added | gnasher729 | timeline score: 2 | |
| Jul 22, 2019 at 17:45 | comment | added | Eric Towers | Do you want worst case performance or average (over the set of initial permutations of $L$) performance? For instance, quickselect is $O(N)$ on average, but $O(N^2)$ in the worst case. | |
| Jul 22, 2019 at 13:28 | vote | accept | yoyostein | ||
| Jul 22, 2019 at 13:22 | comment | added | Simon Richter | Note that computing the mean of a large number of floating point numbers needs more than $O(N)$, typically $O(N\ log\ N)$. | |
| Jul 22, 2019 at 13:19 | history | became hot network question | |||
| Jul 22, 2019 at 9:00 | history | tweeted | twitter.com/StackCompSci/status/1153228319367880704 | ||
| Jul 22, 2019 at 6:36 | answer | added | Yuval Filmus | timeline score: 10 | |
| Jul 22, 2019 at 5:21 | comment | added | Pseudonym♦ | en.wikipedia.org/wiki/Quickselect | |
| Jul 22, 2019 at 5:11 | history | asked | yoyostein | CC BY-SA 4.0 |