Comparing complexity of function

Question

Let's say I have a function that runs in $O(n \lg n)$.

Let's say instead of running this function with a $n$-sized input, I run it $k$ times with an $(n/k)$-sized input, so I want to check if

$$ O(n \lg n) = k \left( O \left( \frac{n}{k} \lg \frac{n}{k} \right) \right)$$

I think it is, because of:

$$ O(n \lg n) = O \left( \frac{kn}{k} \lg \frac{n}{k} \right) = O \left( n \lg \frac{n}{k} \right). $$

Supposing $0 < k \leq n$, as in worst case $k = 1$, we can say that $\dfrac{n} {k}$ is $n$.

Am I right?

In general, will the original $O(n \lg n)$ function be faster or slower? It seems to be slower because what was $\lg n$ now is $\lg \dfrac{n}{k}$ for some $k > 0$.

PS: $\lg = \log_2$

Answer 1

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 > 0$) and $f(0) = 0$ (in the limit), and so for all $k>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>0$.