Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
add comment

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

share|improve this answer
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) –  Hurkyl Apr 13 '12 at 23:09
add comment

Your Answer

 
discard

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.