Timeline for Why does $O(n \log n)$ seem so linear?
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 25, 2019 at 8:12 | comment | added | Raphael | This answer may also be of interest. | |
| Apr 25, 2019 at 6:40 | answer | added | Raphael | timeline score: 1 | |
| Apr 25, 2019 at 6:32 | comment | added | Mr. Sigma. | It might be linear till some constant. | |
| Apr 25, 2019 at 6:32 | comment | added | Raphael | Related question. Also, this answer applies. | |
| Apr 25, 2019 at 6:31 | history | edited | Raphael |
edited tags
|
|
| Apr 25, 2019 at 6:26 | comment | added | John K. | Remember that $\log n$ "is a small constant" for all $n$s you can run an $O( n \log n) $ algorithm on on your computer. | |
| Apr 25, 2019 at 6:22 | comment | added | Andreas V. | Yes I analyzed the worst-case. And when running it, I fed it both random data, and data that would give me the most computations possible. While it's definitely slower when running on the second set of data, it's still linear. | |
| Apr 25, 2019 at 6:13 | comment | added | Discrete lizard♦ | What exactly did you analyse? The worst-case behaviour of the algorithm? Also, note that $O$ denotes upper bounds, so a linear function is within $O(n\log n)$, did you mean that you derived a complexity of $\Theta(n\log n)$? | |
| Apr 25, 2019 at 6:10 | review | First posts | |||
| Apr 25, 2019 at 13:14 | |||||
| Apr 25, 2019 at 6:06 | history | asked | Andreas V. | CC BY-SA 4.0 |