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?


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

  • $\begingroup$ But does it require to have $\alpha \in(0,1)$ ? $\endgroup$ – Jyotish Robin Sep 11 at 15:39
  • $\begingroup$ What do you think? What happens when $\alpha$ is outside that range? $\endgroup$ – Yuval Filmus Sep 11 at 16:32
  • $\begingroup$ I think still the order of both terms remains same. But it goes below the "lower bound". $\endgroup$ – Jyotish Robin Sep 11 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.