text: # 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. 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. Feb 12 '14 at 20:23
  • Try e.g. $p = \sqrt{n}$ and see what happens. Feb 12 '14 at 21:16
  – Raphael
  Feb 13 '14 at 11:34
  • @JukkaSuomela I want that computer!
  – 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)$.
  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$.
explanation: The document contains a math question regarding the comparison of two asymptotic complexities, $O(\log{\frac{n}{p}})$ and $O\left(\frac{\log{n}}{\log{p}}\right)$, where \( p \) is the number of cores and \( n \) is the problem size. The user provides their reasoning and a plot to support their observation, and the document also includes comments and a detailed answer explaining the asymptotic behavior of these functions.
distilabel_metadata.content: Evaluate the user given text extract and determine if it contains a math question and optionally and answer to this question.
  
  Output rules:
  
  1. Briefly describe the document and mention if it contains a question or a question and answer.
  2. Finalize the output with: Label: no-question,question,question-and-answer,multiple-question,multiple-question-and-answer
distilabel_metadata.role: system
distilabel_metadata.content: # 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. 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. Feb 12 '14 at 20:23
  • Try e.g. $p = \sqrt{n}$ and see what happens. Feb 12 '14 at 21:16
  – Raphael
  Feb 13 '14 at 11:34
  • @JukkaSuomela I want that computer!
  – 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)$.
  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$.
distilabel_metadata.role: user
distilabel_metadata.raw_output_q_a_detector_0: The document contains a math question regarding the comparison of two asymptotic complexities, $O(\log{\frac{n}{p}})$ and $O\left(\frac{\log{n}}{\log{p}}\right)$, where \( p \) is the number of cores and \( n \) is the problem size. The user provides their reasoning and a plot to support their observation, and the document also includes comments and a detailed answer explaining the asymptotic behavior of these functions.
  
  Label: question-and-answer