What exactly is polynomial time?

Question

I'm trying to understand algorithm complexity, and a lot of algorithms are classified as polynomial. I couldn't find an exact definition anywhere. I assume it is the complexity that is not exponential. Do linear/constant/quadratic complexities count as polynomial? An answer in simple English will be appreciated :)

Answer 1

Polynomial runtime is defined as a function with a constant exponent. So anything O(n^c) where c is a constant (which includes quadratic O(n²) and cubic O(n³) technically). I think what tends to get confusing is some people refer to something like O(n²) as exponential time (which isn't its true classification). An exponential runtime would be O(2ⁿ).

All the runtimes are based on math formulas. So the best way to understand the differences is look at it's bare minimum math formula and compare it.