Complexity analysis using big - O, Omega and Theta notation

Question

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?

Answer 1

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