Take the 2-minute tour ×
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 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?

share|improve this question
2  
"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
1  
Try e.g. $p = \sqrt{n}$ and see what happens. –  Jukka Suomela Feb 12 at 21:16
1  
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
add comment

1 Answer

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

share|improve this answer
    
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
3  
@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
1  
@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
add comment

Your Answer

 
discard

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.