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?

Answer 1

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(n²) - quadratic time
• O(n^c) - polynomial time
• O(cⁿ) - 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/

Answer 2

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.