David Richerby
  • Member for 7 years, 8 months
  • Last seen more than 2 years ago
  • UK
Is there a complexity between $O(n)$ and $O(n \log n)$
4 votes

There are infinitely many, since $O(n(\log n)^\alpha) \subsetneq O(n(\log n)^\beta)$ for any $\alpha<\beta$. So, in particular, $O(n) = O(n(\log n)^0) \subsetneq O(n(\log n)^\alpha) \subsetneq O(n\...

View answer