algorithm - 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/