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

User · Answer

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

User · Answer

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

User · 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

User · 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

User · Answer

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

User · Answer

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

User · Answer

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

[algorithm] Polynomial time and exponential time

Examples related to algorithm