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$
Comparing complexity of function
complexity theory;time complexity
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$.