Formally, an algorithm is polynomial if there exists a k ∈\(\mathbb{N}\) such that its running time is in O(n ^k ), where n is the size of the input. Here, O(n ^k ) denotes the class of all functions that, for large values of n, grow no faster than c · n ^k for some constant number c (this is the “Big-O notation”). For instance, when k = 1, the running time is linear, and when k = 2, the running time is quadratic in n.