What does $n^{O(1)}$ mean?
It's short-hand for "$n^{f(n)}$ for some function $f(n)\in O(1)$".  In other words, the function is at most $n^c$&nbsp;for some constant&nbsp;$c$.

You can see this by directly substituting the definition of $O(1)$ in the expression.  $g(n)=n^{O(1)}$ if there's constant&nbsp;$c$ such that, for all large enough&nbsp;$n$, $f(n)\leq n^{c\cdot 1} = n^c$.

This includes all polynomially-bounded functions.  For example, for $n&gt;0$,
$$n^2+3n = n^2(1+\tfrac3n) = n^{2+\log(1+3/n)/\log n} = n^{O(1)}\,,$$
since, for $n\geq 3$, we have $1&lt;1+\tfrac3n\leq 2$ and $\log n&gt;1$, so the exponent is between $2+\log 2$ and&nbsp;$2$.