Timeline for What are the characteristics of a $\Theta(n \log n)$ time complexity algorithm?
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 14, 2014 at 10:21 | history | edited | David Richerby | CC BY-SA 3.0 |
Theta, not O
|
| Feb 26, 2013 at 18:32 | comment | added | Joe | @Raphael I know that sorting is redundant with the categories of running times already given. The point is that sorting is sometimes the "bottleneck" and algorithms where at first blush the question isn't about sorting may still have the run-time because sorting is required. | |
| Feb 26, 2013 at 7:36 | comment | added | Raphael | Upvoted for the first paragraph. The second seems redundant, since the linearithmic sorting algorithms we know are either divide & conquer or heapsort. An example for the first category is search of $n$ objects in a binary search tree (or sorted array) of size $n$; on a more abstract level, that can also be seen as divide & conquer, though. | |
| Feb 26, 2013 at 7:04 | history | answered | Joe | CC BY-SA 3.0 |