I am not sure about the difference between $n^{\Omega(1)}$ and $\Omega(n)$. It seems to me that the only difference is that $n^{\Omega(1)}$ can contain some sublinear functions, i.e., $n^{\frac{1}{2}}$, which is not the case for $\Omega{(n)}$. Is there any other differences between these two notations?

  • 2
    $\begingroup$ You just explained what the difference is. $\endgroup$ – Yuval Filmus Nov 7 '19 at 19:28
  • $\begingroup$ @YuvalFilmus So, $n^c \in \Omega(n), \forall 0<c<1$. And for the other, we have: $n^c \in n^{\Omega(1)}, \forall c \in \mathbb{R}$. $\endgroup$ – user777 Nov 18 '19 at 17:44
  • 1
    $\begingroup$ In fact, $n^c = \Omega(n)$ iff $c \geq 1$. $\endgroup$ – Yuval Filmus Nov 18 '19 at 17:46