1
$\begingroup$

I was reading a research paper and there I read the following:

$t=O\left(d^{2} \log _{d}^{2} n\right)$ matches the lower bound $\Omega\left(d^{2} \log _{d} n\right)$ in the regime where $d=\Theta\left(n^{\alpha}\right)$ for some $\alpha \in(0,1)$.

It also says $t=O\left(d^{2} \log n\right)$ outperforms $t=O\left(d^{2} \log _{d}^{2} n\right)$ in the regime where $d=O(\operatorname{poly}(\log n))$

I am not sure how to verify these statements? I understand the basics of all the complexity notations, but how can we mathematically prove this?

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ What research paper were you reading? $\endgroup$ – Yuval Filmus Sep 11 '19 at 15:00
  • $\begingroup$ @YuvalFilmus I was reading arxiv.org/pdf/1711.05403.pdf $\endgroup$ – wanderer Sep 11 '19 at 15:36
  • $\begingroup$ (Page 2, 2nd paragraph) $\endgroup$ – wanderer Sep 11 '19 at 15:43
2
$\begingroup$

When $d = \Theta(n^\alpha)$, we have $\log_d n = \Theta(1)$, and so there is no difference between $d^2\log_d^2 n$ and $d^2\log_d n$ (or rather, the two differ only by a constant factor).

When $d$ is polylogarithmic in $n$, $\log_d n = \log n / \log d = \Theta(\log n/\log \log n)$, and so $\log^2_d n = \Theta((\log n / \log\log n)^2)$ is asymptotically larger than $\log n$.

For what values of $d$ are $\log^2_d n$ and $\log n$ asymptotically the same? We need $\log^2n/\log^2d = \Theta(\log n)$, and so $\log d = \Theta(\sqrt{\log n})$, i.e., $d = 2^{\Theta(\sqrt{\log n})}$. This is more than polylogarithmic but less than polynomial in $n$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ But does it require to have $\alpha \in(0,1)$ ? $\endgroup$ – wanderer Sep 11 '19 at 15:39
  • $\begingroup$ What do you think? What happens when $\alpha$ is outside that range? $\endgroup$ – Yuval Filmus Sep 11 '19 at 16:32
  • $\begingroup$ I think still the order of both terms remains same. But it goes below the "lower bound". $\endgroup$ – wanderer Sep 11 '19 at 16:59

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.