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