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

$\endgroup$
4
  • $\begingroup$ This should answer your question: en.m.wikipedia.org/wiki/Big_O_notation#Multiple_usages $\endgroup$
    – ryan
    Aug 12, 2017 at 15:31
  • 2
    $\begingroup$ You are right to be confused; few authors actually define the notation. $\endgroup$
    – Raphael
    Aug 12, 2017 at 17:21
  • 1
    $\begingroup$ Such notation is commonplace in the literature, and everybody know exactly what it means, despite Raphael's misgivings. $\endgroup$ Aug 12, 2017 at 21:38
  • 1
    $\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, 2017 at 11:33

1 Answer 1

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

$\endgroup$
6
  • 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, 2017 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, 2017 at 17:41
  • $\begingroup$ @ryan: $3n^2 = n^{f(n)}$ where f (n) = 2 + log 3 / log n. $\endgroup$
    – gnasher729
    Aug 12, 2017 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, 2017 at 18:13
  • 1
    $\begingroup$ @Raphael Yes, polynomially bounded -- edited to clarify. $\endgroup$ Aug 12, 2017 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.