Search code examples
algorithm

Polynomial time and exponential time

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?

Solution

  • 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.