# In complexity theory, does polynomial time refer to the big-O notation?

When we are discussing the run time of an algorithm, are we referring to big-O notation or are we saying that the runtime is the same for all cases?

For example; algorithm X runs in polynomial time.

• For example, for stable_sort: "Let $N$ be \tcode{last - first}. If enough extra memory is available, $N \log(N)$ comparisons. Otherwise, at most $N \log^2(N)$ comparisons. In either case, twice as many projections as the number of comparisons." – Jörg W Mittag Jun 22 '19 at 21:19