max degree polynomial for time complexity considerations

396 Views Asked by At

Is there some maximum degree for a polynomial for time complexity considerations and maybe P-NP considerations, maybe some high-degree polynomial formula identified by name, and associated with some well-known theorem, such that you don't really have to ever consider anything higher than that.

I would presume merely for example, that there aren't any known algorithms of say, O(n^15) complexity, and when someone alludes to polynomial time algorithms in the abstract, its assumed that it would never approach the degree of 15 (and maybe a lot less than that).

1

There are 1 best solutions below

5
On

The answer is no - the complexity class $\mathcal P$ consists of all problems that can be solved in polynomial time. In other words, a problem $P$ is in $\mathcal P$ if $$P(n) \in \bigcup_{k=1}^\infty O\left(n^k\right). $$ Suppose $f$ is a function defined on the positive integers with $f(n)\in O(n^k)$ for some $k>1$, but $f(n)\notin O(n^j)$ for $j<k$. Then it is easy to see that $nf(n)\in O(n^{k+1})$. Therefore we can construct an algorithm with runtime $\Theta(n^k)$ for any positive integer $k$.