# Why is log(n/p) asymptotically less than log(n)/log(p)

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:

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?

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

$O(\frac{\log n}{\log p}) = 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(\log \frac{n}{p}) = 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$.

-
Good point. I was incorrect in saying that $p$ is a fixed constant (I've updated the question). It actually represents the parallelism (number of cores), and I'm trying to characterize a parallel algorithm, so I can't just ignore it. The plot is just an example where p=8, though any value I enter for $p$ has the same result. Is there a way to understand this without ignoring the $p$? –  aaronstacy Feb 12 at 20:30
@aaronstacy Ok, 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, 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). –  Gilles Feb 12 at 20:36
@aaronstacy: I suggest you express the runtime in $n$ and $p$, get a $\sim$ asymptotic for it and check what speedup and/of efficiency you get (for $n \to \infty$). –  Raphael Feb 13 at 23:28