1
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Pavan Kumar Munnam Dec 11 '16 at 5:59
  • $\begingroup$ 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 $\endgroup$ – Daniel Dec 11 '16 at 6:22
  • $\begingroup$ Functions are not fast or slow. $\endgroup$ – Yuval Filmus Dec 11 '16 at 8:14
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.