Polynomial time and exponential time
Polynomial time and exponential time
Question
Could someone explain the difference between polynomial-time, non-polynomial-time, and exponential-time algorithms?
For example, if an algorithm takes O(n^2) time, then which category is it in?
Accepted Answer
Check this out.
Exponential is worse than polynomial.
O(n^2) falls into the quadratic category, which is a type of polynomial (the special case of the exponent being equal to 2) and better than exponential.
Exponential is much worse than polynomial. Look at how the functions grow
n = 10 | 100 | 1000
n^2 = 100 | 10000 | 1000000
k^n = k^10 | k^100 | k^1000
k^1000 is exceptionally huge unless k is smaller than something like 1.1. Like, something like every particle in the universe would have to do 100 billion billion billion operations per second for trillions of billions of billions of years to get that done.
I didn't calculate it out, but ITS THAT BIG.
Popular Answer
Below are some common Big-O functions while analyzing algorithms.
- O(1) - constant time
- O(log(n)) - logarithmic time
- O((log(n))c) - polylogarithmic time
- O(n) - linear time
- O(n2) - quadratic time
- O(nc) - polynomial time
- O(cn) - exponential time
- O(n!) - factorial time
(n = size of input, c = some constant)
Here is the model graph representing Big-O complexity of some functions
cheers :-)
graph credits http://bigocheatsheet.com/
Read more... Read less...
O(n^2) is polynomial time. The polynomial is f(n) = n^2. On the other hand, O(2^n) is exponential time, where the exponential function implied is f(n) = 2^n. The difference is whether the function of n places n in the base of an exponentiation, or in the exponent itself.
Any exponential growth function will grow significantly faster (long term) than any polynomial function, so the distinction is relevant to the efficiency of an algorithm, especially for large values of n.
Polynomial time.
A polynomial is a sum of terms that look like Constant * x^k
Exponential means something like Constant * k^x
(in both cases, k is a constant and x is a variable).
The execution time of exponential algorithms grows much faster than that of polynomial ones.
Exponential (You have an exponential function if MINIMAL ONE EXPONENT is dependent on a parameter):
- E.g. f(x) = constant ^ x
Polynomial (You have a polynomial function if NO EXPONENT is dependent on some function parameters):
- E.g. f(x) = x ^ constant
polynomial time O(n)^k means Number of operations are proportional to power k of the size of input
exponential time O(k)^n means Number of operations are proportional to the exponent of the size of input
o(n sequre) is polynimal time complexity while o(2^n) is exponential time complexity if p=np when best case , in the worst case p=np not equal becasue when input size n grow so long or input sizer increase so longer its going to worst case and handling so complexity growth rate increase and depend on n size of input when input is small it is polynimal when input size large and large so p=np not equal it means growth rate depend on size of input "N". optimization, sat, clique, and independ set also met in exponential to polynimal.