# Big-O notation for Polynomial Time Complexity

Recently we had a quiz where one of the question were -

Q: Asymptotic notation for polynomial :

- 2^Ο(n)
- Ο(n log n)
- n^Ο(1)
- None of these


I know that Polynomial time complexity is $$\mathcal{O}(n^c)$$, where $$c$$ is an arbitrary constant.
But then I checked it up on Wikipedia, and it got me confused.

According to Wikipedia, Polynomial Time Complexity is $$2^\mathcal{O(log n)} = poly(n)$$, where $$poly(x) = x^\mathcal{O(1)}$$.

So my questions are -

1. What is the $$Big-O$$ notation for Polynomial Time Complexity and how is it $$2^\mathcal{O(log n)} = poly(n)$$ ?
2. What will be the answer for the quiz ?
I have answered None of these .

Also it has got this line - In the table, poly(x) = x^O(1), i.e., polynomial in x.
What does polynomial in x means ?

• If $poly(x) = x^\mathcal{O(1)}$, then $poly(n) = n^\mathcal{O(1)}$ ? May 14 at 0:28
• @zkutch I think so. In any way, can those two be different ? May 14 at 8:01

The question is worded in a tricky way. When it says "polynomial" it really means "all functions that represent a polynomial complexity class". Essentially, they want the asymptotic notation for the functions $$f(n)=1$$, $$f(n)=n$$, $$f(n)=n^2$$, etc. The reason we want this is because you would see this inside big-O like $$O(1)$$, $$O(n)$$, $$O(n^2)$$, etc. Those functions represent these big-O sets.

The reason we talk about it this way is because we are talking about it in the world of complexity classes. An example is $$P$$.

\begin{align} P = DTIME(poly(n)) = \bigcup\limits_{k\in\mathbb{N}}DTIME(n^k) \end{align}

From the wiki on DTIME.

If a problem of input size $$n$$ can be solved in $$O(f(n))$$, we have a complexity class $$DTIME(f(n))$$ (or $$TIME(f(n))$$).

So the asymptotic notation for the set of these functions is $$n^{O(1)}$$. The following is a way to reason about it. \begin{align} n^{O(1)} &= n^{\{0,1,2,...\}} \\ &= \{1,\ n,\ n^2,\ ...\} \end{align}

To show that $$2^{O(\log n)} = poly(n)$$ is with the same reasoning as above. \begin{align} 2^{O(\log{n})} &= 2^{\{0\cdot\log{n},\ 1\cdot\log{n},\ 2\cdot\log{n},\ ...\}} \\ &= 2^{\{0,\ \log(n^1),\ \log(n^2),\ ...\}} \\ &= \{2^0,\ 2^{\log(n)},\ 2^{\log(n^2)},\ ...\} \\ &= \{1,\ n^1,\ n^2,\ ...\} \\ &= n^{O(1)} \end{align}

To formally show these are equal, you would have to use set notation.

Finally, "polynomial in x" means that $$poly(x)$$ grows polynomially depending on $$x$$. You can see that some of the entries in the table have a function as the argument to $$poly$$. For instance, $$poly(\log{n})$$ (polylogarithmic) grows slower than $$poly(n)$$ (polynomial) since $$O(\log{n}) < O(n)$$.