4.39

The apparent contradiction disappears once the logarithm is simplified: [math]\log(\sqrt n)=\log(n^{1/2})=\tfrac12\log n.[/math] Hence [math]O\!\bigl(n\log(\sqrt n)\bigr)=O\!\bigl(n\cdot\tfrac12\log n\bigr)=O(n\log n).[/math] The Ω(n log n) lower bound only rules out algorithms whose complexity is asymptotically smaller than n log n up to constant factors; it does not forbid a constant ½ in front of the term. Your algorithm therefore matches the lower bound (aside from that constant) rather than breaking it, so there is no conflict.

Back to Chapter 4