Proofs of Algorithm Correctness and Runtime Estimates · Polynomial, Exponential, and Logarithmic Functions

Lesson 5

Nikolai Chukhin · Alexander S. Kulikov

Below are the graphs of four power functions \(n^{k}\) for the exponents \(k=1/2, 1, 3/2, 2\). For \(0< l < k\) the inequality \(n^{l} \le n^{k}\) holds for all positive integers \(n\), and it is strict for \(n>1\).

import matplotlib.pyplot as plt
import numpy as np

n = np.linspace(1, 10)
plt.plot(n, n ** 0.5, label='$n^{0.5}$')
plt.plot(n,  n, label='$n$')
plt.plot(n,  n ** 1.5, label='$n^{1.5}$')
plt.plot(n,  n ** 2, label='$n^2$')
plt.axis([1, 10, 1, 10])
plt.legend()
plt.savefig('polynomial.png')