Mathematical Background

Check your understanding of some mathematical notations and tools.

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 bxb^x denotes the number bb raised to the power of xx.

Press + to interact

If xx is a positive integer, then this is just the value of bb multiplied by itself x1x − 1 times:

bx=b×b××bxb^x = \underbrace{b \times b \times \cdots \times b}_{x}

When xx is a negative integer, bx=1/bxb^x =1 / b^{−x}. When x=0x = 0, bx=1b^x = 1. When bb is not an integer, we can still define exponentiation in terms of the exponential function exe^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 logbk\log_{b}{k} denotes the basebbase–b logarithm of kk. That is, the unique value xx that satisfies

bx=kb^x = k

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

An informal, but useful, way to think about logarithms is to think of logbk\log_{b}{k} as the number of times we have to divide kk by bb before the result is less than or equal to 11. For example, when one does binary search, each comparison reduces the number of possible answers by a factor of 22. This is repeated until there is at most one possible answer. Therefore, the number of comparison done by binary search when there are initially at most n+1n + 1 possible answers is at most log2(n+1)\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 lnk\ln k to denote logek\log_{e} {k}, where eeEuler’s constant—is given by

e=limn(1+1n)n2.71828e = \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:

1k1xdx=lnk\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:

blogbk=kb^{\log_{b}k} = k

and changing the base of a logarithm:

logbk=logaklogab\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.

lnk=logkloge=logk(lne)/(ln2)=(ln2)(logk)0.693147logk\ln k = \frac {\log k} {\log e} = \frac {\log k} {(\ln e) / (\ln 2)} = (\ln 2) (\log k) \approx 0.693147 \log k

In one or two places in this course, the factorial function is used. For a non-negative integer nn, the notation n!n! (pronounced “nn factorial”) is defined to mean

n!=123nn! = 1 \cdot 2 \cdot 3 \cdot \cdots \cdot n ...