Timeline for What are the characteristics of a $\Theta(n \log n)$ time complexity algorithm?
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 14, 2014 at 10:20 | comment | added | Nicolas Miari | I wanted to make the point that I actually searched the internet for $O(n \log n)$ to see if the loop in my answer, that I had to come up with for an actual answer to an actual programming problem that was required to run in $O(n \log n)$, was actually $O(n \log n)$ or not. And most information around deals with divide-and-conquer algorithms, so it would be worth mentioning. I do not pretend my answer to be the archetypical $O(n \log n)$ algorithm. | |
| Nov 14, 2014 at 10:18 | comment | added | David Richerby | Sure but any algorithm that runs in linear or constant time is $O(n\log n)$, as well as being $O(2^{2^n})$ and $O(\text{almost anything else})$. Your answer has nothing to do with logarithms. If you want to make the point that the question should be asking about $\Theta(n\log n)$ rather than $O(n\log n)$ then either make that point explicitly as comment to the question or, even better, edit the question. | |
| Nov 14, 2014 at 10:17 | comment | added | Nicolas Miari | additionally, the original question didn't ask for big-theta. | |
| Nov 14, 2014 at 10:15 | comment | added | Nicolas Miari | I thought it useful to mention, since it does come up in practice but every search for "$O(n \log n)$" is mostly "divide-and-conquer" examples like e.g. merge sort. | |
| Nov 14, 2014 at 10:12 | comment | added | David Richerby | Yes, these are both $O(n\log n)$ but for the trivial reason that the bound is not tight. The first one is $\Theta(n)$ and the second is $\Theta(1)$ (or $\Theta(|n|)$ if $n$ can be negative). | |
| Nov 14, 2014 at 10:02 | review | First posts | |||
| Nov 14, 2014 at 10:13 | |||||
| Nov 14, 2014 at 9:57 | history | answered | Nicolas Miari | CC BY-SA 3.0 |