5
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ This should answer your question: en.m.wikipedia.org/wiki/Big_O_notation#Multiple_usages $\endgroup$ – ryan Aug 12 '17 at 15:31
  • 1
    $\begingroup$ You are right to be confused; few authors actually define the notation. $\endgroup$ – Raphael♦ Aug 12 '17 at 17:21
  • 1
    $\begingroup$ Such notation is commonplace in the literature, and everybody know exactly what it means, despite Raphael's misgivings. $\endgroup$ – Yuval Filmus Aug 12 '17 at 21:38
  • $\begingroup$ @YuvalFilmus And yet, every time such a question comes up, people who "know exactly what it means" struggle to explain what that is, exactly. $\endgroup$ – Raphael♦ Aug 13 '17 at 11:33
8
$\begingroup$

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$.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ I recall this thread where a disagreement became clear. Just to clarify: you are proposing that $n^{O(1)}$ is the set of all polynomially bounded functions, correct? $\endgroup$ – Raphael♦ Aug 12 '17 at 17:24
  • $\begingroup$ @Raphael, wouldn't it just be the set of all monomial functions with coefficient $1$? e.g. $n^3 + n^2 \notin n^{O(1)}$ and $3n^2 \notin n^{O(1)}$ because they don't follow the form of $n$ to some power $O(1)$. Is this correct? $\endgroup$ – ryan Aug 12 '17 at 17:41
  • $\begingroup$ @ryan: $3n^2 = n^{f(n)}$ where f (n) = 2 + log 3 / log n. $\endgroup$ – gnasher729 Aug 12 '17 at 17:46
  • 1
    $\begingroup$ Aaaaand we once again have proof that such notation is incomprehensible and should be avoided. :'D $\endgroup$ – Raphael♦ Aug 12 '17 at 18:13
  • 1
    $\begingroup$ @Raphael Yes, polynomially bounded -- edited to clarify. $\endgroup$ – David Richerby Aug 12 '17 at 21:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.