I'm trying to figure out which is better asymptotic complexity, $O(\log{\frac{n}{p}})$ or $O\left(\frac{\log{n}}{\log{p}}\right)$. $p$ is the amount of parallelism (i.e. number of cores), and $n$ is the problem size. When I plot them in Grapher.app with any constant value for $p$, the first looks better:

enter image description here

But when I try to work out the math it doesn't seem right:

$$ O(\log{\frac{n}{p}}) = O(\log{n} - \log{p}) $$

$O\left(\frac{\log{n}}{\log{p}}\right)$ seems like a better bound than the above since it divides by $\log{p}$ instead of just subtracting it. What am I missing?

  • 2
    $\begingroup$ "Better complexity" - you can't see that from that plot, Landau notation hides constant factors and lower order terms. $\endgroup$
    – G. Bach
    Feb 12 '14 at 17:44
  • $\begingroup$ i was incorrect in saying "p is a fixed constant." i'm trying to characterize asymptotic behavior for parallel algorithms, so p is the number of cores. the plot is meant to be an example with p=8. i'll correct the wording. $\endgroup$
    – aaronstacy
    Feb 12 '14 at 20:23
  • 1
    $\begingroup$ Try e.g. $p = \sqrt{n}$ and see what happens. $\endgroup$ Feb 12 '14 at 21:16
  • 1
    $\begingroup$ Your question is answered by combining this and this. $\endgroup$
    – Raphael
    Feb 13 '14 at 11:34
  • $\begingroup$ @JukkaSuomela I want that computer! $\endgroup$
    – Raphael
    Feb 13 '14 at 11:34

I assume that $p > 1$ (which is equivalent to $\log p > 0$, otherwise we have negative-valued functions which are meaningless as complexity measures.

For a given $p$, $O\left(\frac{\log n}{\log p}\right) = O(\log n)$ since big oh isn't affected by multiplication by a positive constant.
$\log \frac{n}{p} = \log n - \log p$. Since $\log p = o(\log n)$, $O\left(\log \frac{n}{p}\right) = O(\log n)$.

So up to big-oh complexity (or big-theta, for the same reasons), these two classes are the same.

Your diagram doesn't show a visual difference: you need to bring the two curves to the same scale. One is $a \log n$ for some constant $a > 0$, the other is $\log n + b$ for some constant $b$.

If you want to study the variation in $p$, then $O$ or $\Theta$ with respect to the variable $n$ are not good ways of modeling the complexity of your problem. You need more precise approximations that treat multiplicative constants as relevant. The complexity in $p$ is probably relevant to your problem, and is very different. I'm not familiar enouhg with parallelism to know whether it's the right measure to use here, this could warrant a separate question (with more information about what you're modeling). You're going to need express the complexity in terms of $n$ and $p$, and look at how the variation in $p$ (not the complexity itself) behaves for large $n$.


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.