I read an example that said explain what "$f(n)$ is $n^{O(1)}$" means.
I can't interpret the $n^{O(1)}$ syntax. I know what Big $O$ notation is, its just that this example looks odd to me.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityI read an example that said explain what "$f(n)$ is $n^{O(1)}$" means.
I can't interpret the $n^{O(1)}$ syntax. I know what Big $O$ notation is, its just that this example looks odd to me.
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$ for some constant $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 $c$ such that, for all large enough $n$, $f(n)\leq n^{c\cdot 1} = n^c$.
This includes all polynomially-bounded functions. For example, for $n>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<1+\tfrac3n\leq 2$ and $\log n>1$, so the exponent is between $2+\log 2$ and $2$.