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$
    – zkutch
    May 14 at 0:28
  • $\begingroup$ @zkutch I think so. In any way, can those two be different ? $\endgroup$ May 14 at 8:01
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.