Mathematical Background

In this lesson, we review some mathematical notations and tools used throughout this course, including logarithms, big-Oh notation, and probability theory. This review will be brief and is not intended as an introduction.

Exponentials and logarithms

The expression $b^x$ denotes the number $b$ raised to the power of $x$.

The expression $b^x$ denotes the number $b$ raised to the power of $x$. If $x$ is a positive integer, then this is just the value of $b$ multiplied by itself $x − 1$ times:

$$b^x = \underbrace{b \times b \times \cdots \times b}_{x}$$

When $x$ is a negative integer, $b^x =1 / b^{−x}$. When $x = 0$, $b^x = 1$. When $b$ is not an integer, we can still define exponentiation in terms of the exponential function $e^x$ (see below), which is itself defined in terms of the exponential series, but this is best left to a calculus text.

In this course, the expression $\log_{b}{k}$ denotes the $base–b$ logarithm of $k$. That is, the unique value $x$ that satisfies

$$b^x = k$$

Most of the logarithms in this course are base 2 (binary logarithms). For these, we omit the base, so that $\log_k$ is shorthand for $\log_{2}{k}$.

An informal, but useful, way to think about logarithms is to think of $\log_{b}{k}$ as the number of times we have to divide $k$ by $b$ before the result is less than or equal to $1$. For example, when a binary search is done, each comparison reduces the number of possible answers by a factor of $2$. This is repeated until there is at most one possible answer. Therefore, the number of comparisons done by binary search, when there are initially at most $n + 1$ possible answers, is at most $\lceil \log_2(n + 1) \rceil$.

Another logarithm that comes up several times in this course is the natural logarithm. Here we use the notation $\ln k$ to denote $\log_{e} {k}$, where $e$—Euler’s constant—is given by

$$e = \lim_{n\to\infty}\left(1+\frac{1}{n}\right)^n \approx 2.71828$$

The natural logarithm comes up frequently because it is the value of a particularly common integral:

$$\int_{1}^{k} \frac{1}{x} dx = \ln k$$

Two of the most common manipulations we do with logarithms are removing them from an exponent:

$$b^{\log_{b}k} = k$$

and changing the base of a logarithm:

$$\log_{b}k = \frac {\log_{a} k} {\log_{a} b}$$

For example, we can use these two manipulations to compare the natural and binary logarithms.

$$\ln k=\frac{\log k}{\log e}=\frac{\log k}{(\ln e}$$ ...