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

Lesson 4

Nikolai Chukhin · Alexander S. Kulikov

In the following steps, we recall the behavior of three functions most often encountered in discrete mathematics.

Power function (or polynomial): \(n^{k}\), where the constant \(k>0\) is called the exponent.

Exponential function (or exponent): \(c^{n}\), where the constant \(c>1\) is called the base of the exponent.

Logarithmic function (or logarithm): \(\log_{b} n\), where the constant \(b>1\) is called the base of the logarithm.

In discrete mathematics, the parameter of these functions is usually denoted by the letter \(n\), because almost always \(n\) will be an integer. But sometimes (for example, when plotting these functions), we will assume that \(n \ge 1\) is a positive real number.

It is easy to see that each of these functions increases indefinitely with the growth of \(n\): as \(n\) increases, so does the value of the function, and for any number, there will be a value of \(n\) at which the function value will be greater than this number.