Values of k that make this true, $\log^k n \in \Omega(\sqrt n)$
Let's redo your calculation. You want
$$ \log^kn \geq C \sqrt{n} $$
to hold for some $C&gt;0$ and large $n$. Taking the logarithm,
$$
k \log \log n \geq \log C + \tfrac{1}{2}\log n,
$$
and so
$$
k \geq \frac{\log C + \tfrac{1}{2}\log n}{\log\log n}
$$
should hold for large $n$. In other words,
$$
k = \frac{\log n}{2\log\log n} + \Omega\left(\frac{1}{\log\log n}\right).
$$