Hot answers tagged

2

$\Omega(\cdot)$ means “at least that many steps” _up to a multiplicative constant. There's a gap between $n!$ and $n^n$, and that gap is more than a multiplicative constant. But we aren't looking for an asymptotic bound on the number of length of the list that can be sorted in $k$ steps, but on the minimum number of steps $S(n)$ that it takes to sort a list ...


1

Stirling's approximation shows that $$ \log (n!) = \Theta(n\log n). $$


1

Natural Mergesort usually refers to Timsort. In terms of comparison to bottom-up mergesort, Timsort has $O(n)$ best-case running time where as bottom-up mergesort is at least $O(n\log n)$ on any input. However, analysis of the worst-case running time of Timsort proves to be more tricky; an 2018 paper [1] establishes that its worst-case time complexity is $O(...


Only top voted, non community-wiki answers of a minimum length are eligible