News for hackers. Stuff that matters.
Re:Big-O Algorithm Complexity Cheat Sheet by dhruvbird on Sunday May 05, 2013 @02:20PM (#5659200)
Actually, it's useful when 'N' (the number of elements) is much larger than 'k', the number of significant digits in the largest number in the set.

If k ∈ Θ(log N), then O(Nk) becomes O(N log N), which is asymptotically no better than any optimal comparison based sort.

However, if k ∈ o(log N), then we get an asymptotically better algorithm.

There are no comments on this comment yet.