Sign up ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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 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?

share|cite|improve this question
"Better complexity" - you can't see that from that plot, Landau notation hides constant factors and lower order terms. – G. Bach Feb 12 '14 at 17:44
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. – aaronstacy Feb 12 '14 at 20:23
Try e.g. $p = \sqrt{n}$ and see what happens. – Jukka Suomela Feb 12 '14 at 21:16
Your question is answered by combining this and this. – Raphael Feb 13 '14 at 11:34
@JukkaSuomela I want that computer! – Raphael Feb 13 '14 at 11:34

1 Answer 1

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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