-1
$\begingroup$

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

  • 0
    The answers to [this question](http://math.stackexchange.com/questions/86076/what-are-the-rules-for-equals-signs-with-big-o-and-little-o) may be helpful.2012-04-13

1 Answers 1

-1

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

  • 2
    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)2012-04-13