T(n) is O(f (n)), read as “T(n) is order f (n)”.
Given another function f (n), we say that T(n) is O(f (n)) (read as “T(n) is order f (n)”) if, for sufficiently large n, the function T(n) is bounded above by a constant multiple of f (n). We will also sometimes write this as T(n) = O(f (n)). More precisely, T(n) is O(f (n)) if there exist constants c > 0 and n0 ≥ 0 so that for all n ≥ n0, we have T(n) ≤ c · f (n). In this case, we will say that T is asymptotically upperbounded by f . It is important to note that this definition requires a constant c to exist that works for all n; in particular, c cannot depend on n.
Using O(·) notation, it’s easy to formally define polynomial time: a polynomial-time algorithm is one whose running time T(n) is O(nd) for some constant d, where d is independent of the input size.
We will see many algorithms whose running times have the form O(n log n). Such algorithms are also polynomial time: as we will see next, log n ≤ n for all n ≥ 1, and hence n log n ≤ n2 for all n ≥ 1. In other words, if an algorithm has running time
O(n log n), then it also has running time O(n2), and so it is a polynomial-time
algorithm.
