# Comparing complexity of function

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$

• yeah, it seems ok ,but after dividing it you need to rejoin the problems right, for example you are Sorting a N input size by a heap sort to get a sorted, but now you are doing for N/K size but that results in N/K sorted lists not original sorted list we got at the start by using it on the N size – Pavan Kumar Munnam Dec 11 '16 at 5:59
• I don't need (in this specific case the subproblems don't need to fit together), its like sort a full array vs sort all consecutive blocks k-sized of the same array – Daniel Dec 11 '16 at 6:22
• Functions are not fast or slow. – Yuval Filmus Dec 11 '16 at 8:14

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$.