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

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)}$

-
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

## 1 Answer

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

-
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