Problem Detail: I’m trying to understand algorithm complexity, and a lot of algorithms are classified as polynomial. I couldn’t find an exact definition anywhere. I assume it is the complexity that is not exponential. Do linear/constant/quadratic complexities count as polynomial? An answer in simple English will be appreciated 🙂
Asked By : Oleksiy
Answered By : Yuval Filmus
An algorithm is polynomial (has polynomial running time) if for some $k,C>0$, its running time on inputs of size $n$ is at most $Cn^k$. Equivalently, an algorithm is polynomial if for some $k>0$, its running time on inputs of size $n$ is $O(n^k)$. This includes linear, quadratic, cubic and more. On the other hand, algorithms with exponential running times are not polynomial. There are things in between – for example, the best known algorithm for factoring runs in time $O(exp(Cn^{1/3} log^{2/3} n))$ for some constant $C > 0$; such a running time is known as sub-exponential. Other algorithms could run in time $O(exp(Alog^C n))$ for some $A > 0$ and $C > 1$, and these are known as quasi-polynomial. Such an algorithm has very recently been claimed for discrete log over small characteristics.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/13625
