1
$\begingroup$

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 ?

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

1 Answer 1

2
$\begingroup$

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

$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.