Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I must use O notation to show that:

$T(n) = n^{O(1)}$ iff exists $k > 0$ such that $T(n) = O(n^k)$

But, I don't understand what mean: $n^{O(1)}$

share|cite|improve this question
Anybody knows? please. – Albert Apr 13 '12 at 20:41
Maybe you know the meaning of $O(1)$? – Did Apr 13 '12 at 21:39
$f(n)=O(1)$ means that there is some large $N$ such that $f(n)\leq C$ for some constant $C$ and all $n\geq N$. Notice that you need to show that $T(n)\leq C' n^k$ for all $n\geq N'$ for some $N'$. – Alex R. Apr 13 '12 at 21:39
The answers to this question may be helpful. – Henning Makholm Apr 13 '12 at 22:39

The function $g(n) = n^{O(1)}$ means that there is some function $f(n)$ such that $g(n) = n^{f(n)}$, and $f(n) = O(1)$. In other words, $f(n)$ is just some constant value $f$, and so $g(n) = n^f$.

Suppose $T(n) = n^{O(1)}$. So $T(n) = n^f$ for some constant $f$. So $T(n) = O(n^f)$.

Suppose $T(n) = O(n^k)$. So $T(n) \leq C n^k$ for some constant $C$.

There is a slight technical hiccup here, depending on how the $O()$ notation is defined. Usually it is defined as applying for $n$ sufficiently large. We will adopt this position here.

Now note that for $n \geq 2$ we have $C \leq n^C$. So, for $n \geq 2$, we have $T(n) \leq n^{C} n^k = n^{C+k}$. Here $C$ and $k$ are constants, so $C+k = O(1)$. So $T(n) = n^{O(1)}$.

share|cite|improve this answer
The class $O(1)$ is not that of constant functions; it's that of bounded functions. (or eventually bounded functions, depending on the technical detail) – Hurkyl Apr 13 '12 at 23:09

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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