Values of k that make this true, $\log^k n \in \Omega(\sqrt n)$ I have seen some algorithms with complexities like $\log^3 n$ and $\sqrt n$. In view of getting a better idea on how to compare these I wanted to know for which values of $k$ does $\log^k n \in \Omega(\sqrt n)$ hold true?

I suspect $k$ would need to be a function of $n$. Because if it were a constant $C_1$, we could always find a larger constant $C_2$ that makes the previous statement false.  

This is what I have tried.

$\log^k n \in \Omega(\sqrt n)$

$\log^{2k} n \in \Omega(n)$

$\log(\log^{2k}n) \in \Omega(\log n)$

$2k \log\log n \in \Omega(\log n)$

From here, I can see that if $k$ is $\log n$, then $2\log n \log\log n \in \Omega(\log n)$ is true.

However, I doubt this is a tight bound.
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).
$$