Comparing complexity of function
If a function $f$ is convex and $f(0) = 0$ then $f$ is superadditive: $f(a+b) \geq f(a) + f(b)$ for $a,b \geq 0$. The function $f(n) = n\log n$ is convex (since $f''(n) = 1/n &gt; 0$) and $f(0) = 0$ (in the limit), and so for all $k&gt;0$,
$$
f(n) \geq k f(n/k).
$$
If $f$ were concave rather than convex, $f$ would be subadditive, and then $f(n) \leq kf(n/k)$ for all $k&gt;0$.