Proofs of Algorithm Correctness and Runtime Estimates · Polynomial, Exponential, and Logarithmic Functions
Lesson 5
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') 