-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
    Anybody knows? please.2012-04-13
  • 0
    Maybe you know the meaning of $O(1)$?2012-04-13
  • 0
    $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'$.2012-04-13
  • 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