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

Lesson 7

Nikolai Chukhin · Alexander S. Kulikov

Below are the plots of three logarithmic functions \(\log_{b} n\), for the bases \(b=2, e, 10\) (for \(b=e\), it becomes the natural logarithm, denoted as \(\ln n\)). For \(1< a < b\) the inequality \(\log_{b} n \le \log_{a} n\) 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(0.1, 10)
plt.plot(n, np.log2(n), label='$\log_2(n)$')
plt.plot(n, np.log(n), label='$\ln(n)$')
plt.plot(n, np.log10(n), label='$\log_{10}(n)$')
plt.axis([0, 10, 0, 10])
plt.legend()
plt.savefig('logarithmic.png')

The logarithmic function \(\log_{b} n\) is the inverse of the exponential function \(b^{n}\). For example, if \(\log_{2} n=t\), then \(2^{t}=n\), that is, \(2^{\log_2 n}=n\). This reads as: \(\log_{2} n\) is the number to which two must be raised to obtain \(n\). Therefore, the graphs of the two functions are reflections of each other relative to the line \(y=x\):

import matplotlib.pyplot as plt
import numpy as np

n = np.linspace(1, 10)
plt.plot(n,  2 ** n, label='$y=f(n)=2^n$')
plt.plot(n,  n, 'g--', label='$y=n$')
plt.plot(n, np.log2(n), label='$y=f^{-1}(n)=\log_2 n$')
plt.axis([1, 10, 1, 10])
plt.legend()
plt.savefig('log_exp.png')