Content deleted Content added
→Usage of bigO notation. "At least O(...)": new section |
|||
Line 624:
: They are the same algorithm. You can view the linked list as supplying an extra O(n) space for making a stable partition; the array version doesn't have that extra space, so it cannot do a stable partition. [[User:Glrx|Glrx]] ([[User talk:Glrx|talk]]) 21:00, 26 August 2015 (UTC)
== Usage of bigO notation. "At least O(...)" ==
Big-O should denote upper bounds, and Big-Omega denotes lower bounds. I realize that at least colloquially, people don't pay that much attention and say Big-O in all cases, often intending a meaning closer to that of Big-Theta (the conjunction of Big-O and Big-Omega), but that is incorrect usage and should be corrected on Wikipedia, or am I missing a semi-formal convention which standardizes that usage? At the very least [[Big_O_notation|the article on Big-O notation]] seems to agree with me at a quick glance.
"A fundamental limit of comparison sorting algorithms is that they require linearithmic time – O(n log n) – in the worst case"
"Comparison-based sorting algorithms (...) need at least O(n log n) comparisons for most inputs."
"These are all comparison sorts, and so cannot perform better than O(n log n) in the average or worst case."
| |||