# Complexity analysis using big - O, Omega and Theta notation

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?

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

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$$.
• But does it require to have $\alpha \in(0,1)$ ? – wanderer Sep 11 '19 at 15:39
• What do you think? What happens when $\alpha$ is outside that range? – Yuval Filmus Sep 11 '19 at 16:32