Polynomial algorithms are algorithms that have a runtime that is a polynomial function of the input size. This means that the runtime is a function of the form n^k
where k
is a constant. For example, the runtime of the following algorithm is n^2
:
def polynomial_algorithm(n):
for i in range(n):
for j in range(n):
print(i, j)
Visit the following resources to learn more: