CSE 373, Winter 2019: Math Review

Overview

This document covers a few mathematical constructs that appear very frequently when doing algorithmic analysis. We will spend only minimal time in class reviewing these concepts, so if you're unfamiliar with the following concepts, please be sure to read this document and head to office hours if you have any follow-up questions.

We also have a few practice problems located at the bottom of this doc if you're very rusty and want some practice.

(Note: this document was co-written with Meredith Wu)

Exponents

Overview

Exponentiation is often thought of as repeated multiplication. For example, the expression \(b^x\) is equivalent to the following when \(x\) is an integer:

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

We say here that \(b\) is the base and that \(x\) is the exponent.

What happens if \(x\) is zero, or \(x\) is negative? In those cases, the exponent is defined to behave as follows:

  • \(\displaystyle b^0 = 1\)
  • \(\displaystyle b^{-x} = \frac{1}{b^x}\)

(Note that neither the base nor the exponent needs to be integers. However, explaining how exponentiation works in these cases is beyond the scope of this document and isn't too relevant to this course.)

One example where exponents appear in code is if we had a loop that starts by performing operation then performs double that amount with each iteration. If we keep doubling the amount of work done, the code would be doing \(2^n\) operations on the \(n^\text{th}\) iteration.

Useful exponent identities

  1. Power of a power

    Rule:

    \(\displaystyle (b^x)^y = b^{xy} \)

    Example:

    \(\displaystyle (b^2)^4 = (b \cdot b) \cdot (b \cdot b) \cdot (b \cdot b) \cdot (b \cdot b) = b^8 \)

  2. Multiplying exponents

    Rule:

    \(\displaystyle (b^x)\cdot(b^y) = b^{x+y} \)

    Example:

    \(\displaystyle (b^2)\cdot(b^3) = (b \cdot b) \cdot (b \cdot b \cdot b) = b^5 \)

  3. Dividing exponents

    Rule:

    \(\displaystyle \frac{b^x}{b^y} = b^{x-y} \)

    Example:

    \(\displaystyle \frac{b^5}{b^3} = \frac{b \cdot b \cdot b \cdot b \cdot b}{b \cdot b \cdot b} = b^2\) \(\displaystyle \frac{b^3}{b^5} = \frac{b \cdot b \cdot b}{b \cdot b \cdot b \cdot b \cdot b} = \frac{1}{b^2} = b^{-2} \)

  4. Taking the power of two multiplied terms

    Rule:

    \(\displaystyle (a \cdot b)^x = (a^x) \cdot (b^x) \)

    Example:

    \(\displaystyle (a \cdot b)^2 = (a \cdot b) \cdot (a \cdot b) = (a \cdot a) \cdot (b \cdot b) = a^2 \cdot b^2 \)

Logarithms

Overview

The logarithm operation is defined as the inverse of exponentials. For example, suppose we know \(b^x = n\); that is, we know that \(n\) is \(b\) to the power of \(x\). In that case, we also know \(x = \log_b(n)\); that is, we say that \(x\) is the logarithm of \(n\) with the base \(b\).

Here are some examples of equations using logs:

  • \(\displaystyle \log_3(27) = 3\)
  • \(\displaystyle \log_2(16) = 4\)

One important rule to keep in mind is that the logarithm is not defined when \(n = 0\). This makes sense when you remember that logarithms and exponents are inverses of each other: there are no possible values of \(b\) and \(x\) that can make \(b^x = 0\) true, which means that it is again impossible to find values of \(b\) and \(x\) that can make \(x = \log_b(0)\) true.

Because computers are binary systems, within this course, and within computer science in general, we treat the expression \(\log(n)\) and \(\log_2(n)\) as being exactly equivalent – that is, if we omit the base, we assume it's always equal to 2.

So, in the context of this course, \(\log_2(16) = \log(16) = 4\).

We will see many examples of the log operation in use when we begin analyzing trees and recursive functions later this quarter.

Useful logarithm identities

Note: we assume here that in all cases, variables are non-zero.

  1. Log of a product

    Rule:

    \(\displaystyle \log_b(x\cdot y) = \log_b(x) + \log_b(y) \)

    Example:

    \(\displaystyle \log_2(4 \cdot 8) = \log_2(32) = 5 = 2 + 3 = \log_2(4) + \log_2(8) \)

  2. Log of a fraction

    Rule:

    \(\displaystyle \log_b\left(\frac{x}{y}\right) = \log_b(x) - \log_b(y) \)

    Example:

    \(\displaystyle \log_2\left(\frac{32}{4}\right) = \log_2(8) = 3 = 5 - 2 = \log_2(32) - \log_2(4) \)

  3. Log of a power

    Rule:

    \(\displaystyle \log_b(x^y) = y \cdot \log_b(x) \)

    Example:

    \(\displaystyle \log_2(4^3) = \log_2(64) = 6 = 3 \cdot 2 = 3 \cdot \log_2(4) \)

  4. Power of a log

    Rule:

    \(\displaystyle x^{\log_b(y)} = y^{\log_b(x)} \)

    Example:

    \(\displaystyle 4^{\log_2(8)} = 4^{3} = 4 \cdot 4 \cdot 4 = 8 \cdot 8 = 8^2 = 8^{\log_2(4)} \)

  5. Change of base

    Rule:

    \(\displaystyle \log_b(x) = \frac{\log_d(x)}{\log_d(b)} \)

    Example:

    \(\displaystyle \log_2(9) = 3.16992... = \frac{\log_3(9)}{\log_3(2)} \)

Summation

Overview

The summation (\(\sum\)) is a way of concisely expressing the sum of a series of related values. For example, suppose we wanted a concise way of writing \(1 + 2 + 3 + \cdots + 8 + 9 + 10\). We can do so like this:

$$ \sum_{i=1}^{10} i $$

The "\(i = 1\)" expression below the \(\sum\) symbol is initializing a variable called \(i\) which is initially set to 1. We then increase \(i\) by one from that initial value up to and including the number at the top of the \(\sum\) symbol. We then take each value of \(i\) and substitute it to the expression to the right of the \(\sum\) symbol, and add each of those expressions together.

Here is another example:

$$ \begin{align*} \sum_{i=1}^3 2 + i^2 &= (2 + 1^2) + (2 + 2^2) + (2 + 3^2) \\ &= 3 + 6 + 11 \\ &= 20 \end{align*} $$

More generally, the summation operation is defined as follows:

$$ \sum_{i=a}^b f(i) = f(a) + f(a + 1) + f(a + 2) + \cdots + f(b - 2) + f(b - 1) + f(b) $$

...where \(a, b\) are integers such that \(a \leq b\) and \(f(x)\) is some arbitrary function.

One thing to note is that the bounds of a summation are inclusive: in the examples above, \(i\) varies from \(a\) up to and including \(b\).

We will see examples of summations in use when analyzing the behavior of loops later this quarter.

Useful summation identities

Note: you can also download these identities as a pdf.

  1. Splitting a sum

    Rule:

    \(\displaystyle \sum_{i=a}^b (x + y) = \sum_{i=a}^b x + \sum_{i=a}^b y \)

    Example:

    \(\displaystyle \sum_{i=1}^{10} (5 + 7) = 120 = 50 + 70 = \sum_{i=1}^{10} 5 + \sum_{i=1}^{10} 7 \)

  2. Adjusting summation bounds

    Rule:

    \(\displaystyle \sum_{i=a}^b f(x) = \sum_{i=0}^b f(x) - \sum_{i=0}^{a - 1} f(x) \)

    Example:

    \(\displaystyle \sum_{i=5}^{8} i = 5 + 6 + 7 + 8 = \sum_{i=0}^{8} i - \sum_{i=0}^{4} i \)

  3. Factoring out a constant

    Rule:

    \(\displaystyle \sum_{i=a}^b cf(i) = c \sum_{i=a}^b f(i) \)

    Note: \(c\) is some constant.

    Example:

    \(\displaystyle \sum_{i=1}^5 10n = 10\sum_{i=1}^5 n \)

  4. Summation of a constant

    Rule:

    \(\displaystyle \sum_{i=0}^{n-1} c = \underbrace{c + c + \cdots + c}_{\text{$n$ times}} = cn \)

    Note: \(c\) is some constant. This rule is a special case of the previous one.

    Example:

    \(\displaystyle \sum_{i=0}^{5-1} 10 = 10 + 10 + 10 + 10 = 10 = 50 \)

  5. Gauss's identity

    Rule:

    \(\displaystyle \sum_{i=0}^{n-1} i = \frac{n(n - 1)}{2} \)

    Example:

    \(\displaystyle \sum_{i=0}^{10-1} i = \frac{10(9)}{2} = 45 \)

  6. Sum of squares

    Rule:

    \(\displaystyle \sum_{i=0}^{n-1} i^2 = \frac{n(n - 1)(2n - 1)}{6} \)

    Example:

    \(\displaystyle \sum_{i=0}^{10-1} i^2 = \frac{10 \cdot 9 \cdot 19}{6} = 285 \)

  7. Finite geometric series

    Rule:

    Applicable only when \(x \ne 1\).

    \(\displaystyle \sum_{i=0}^{n-1} x^i = \frac{x^n - 1}{x - 1} \)

    Example:

    \(\displaystyle \sum_{i=0}^{10 - 1} 5^i = \frac{5^{10} - 1}{5 - 1} = 2441406 \)

  8. Infinite geometric series

    Rule:

    Applicable only when \(-1 < x < 1\).

    \(\displaystyle \sum_{i=0}^\infty x^i = \frac{1}{1 - x} \)

    Example:

    \(\displaystyle \sum_{i=0}^\infty \left(\frac{1}{2}\right)^i = \frac{1}{1 - 1/2} = 2 \)

Comparison of different functions

We will spend a fair amount of time comparing the relative growth rates of different functions. Here is a plot of several different functions (note that the verical axis has a logarithmic scale):

Practice problems: exponents and logs

  1. If \(a = \log(n)\), what is \(2^a\)?
  2. Show that \(\log_b(b^x) = x\).
  3. Solve \(7 + 15 \cdot 11^{1-3x} = 10\) in terms of \(x\). (Hint: we can take the log of both sides of the equation. Consider: why is it ok to do this?)
  4. Solve \(2^{t^2 - t} = 4\).

Solutions

Problem 1: If \(a = \log(n)\), what is \(2^a\)?

$$ \begin{align*} 2^{\log(n)} &= 2^{\log_2(n)} \\ &= n^{\log_2(2)} \\ &= n^1 \\ &= n \end{align*} $$

Problem 2: Show that \(\log_b(b^x) = x\).

$$ \begin{align*} \log_b(b^x) &= x \log_b(b) \\ &= x \end{align*} $$

Problem 3: Solve \(7 + 15 \cdot 11^{1-3x} = 10\) in terms of \(x\).

$$ \begin{align*} 7 + 15 \cdot 11^{1-3x} &= 10 \\ 15 \cdot 11^{1-3x} &= 3 \\ 11^{1-3x} &= \frac{1}{5} \\ \log_{11}\left(11^{1-3x}\right) &= \log_{11}\left(\frac{1}{5}\right) \\ 1 - 3x &= \log_{11}\left(\frac{1}{5}\right) \\ x &= \frac{1}{3} -\frac{1}{3} \log_{11}\left(\frac{1}{5}\right) \end{align*} $$

Problem 4: Solve \(2^{t^2 - t} = 4\).

$$ \begin{align*} 2^{t^2 - t} &= 4 \\ \log_2\left(2^{t^2 - t}\right) &= \log_2(4) \\ (t^2 - t)\log_2\left(2\right) &= \log_2(4) \\ (t^2 - t) &= 2 \\ t^2 - t - 2 &= 0 \\ (t - 2)(t + 1) &= 0 \end{align*} $$ Therefore, there are two solutions: \(t = 2\) and \(t = -1\).

Practice problems: Summations

  1. Simplify \(\displaystyle \sum_{k=1}^n k(k + 1)\)
  2. Show that the sum of the first \(n\) positive odd integers is \(n^2\).
  3. Simplify \(\displaystyle \sum_{k=1}^n (n-k)\).
  4. Simplify \(\displaystyle \sum_{k=0}^n 2^k\).
  5. Show that \(\displaystyle \sum_{k=1}^{\infty} \frac{1}{2^k}\) converges to 1.

Solutions

Problem 1: Simplify \(\displaystyle \sum_{k=1}^n k(k + 1)\)

$$ \begin{align*} \sum_{k=1}^n k(k+1) &= \sum_{k=1}^n k^2+k \\ &= \frac{n(n+1)(2n+1)}{6} + \frac{n(n+1)}{2} \end{align*} $$

Problem 2: Show that the sum of the first \(n\) positive odd integers is \(n^2\).

$$ \begin{align*} \sum_{k=1}^n (2k - 1) &= 2 \sum_{k=1}^n k - \sum_{k=1}^n 1\\ & = 2 \frac{n(n+1)}{2} - n \\ & = n^2 \end{align*} $$

Problem 3: Simplify \(\displaystyle \sum_{k=1}^n (n-k)\).

$$ \begin{align*} \sum_{k=1}^n (n-k) &= (n-1) + (n-2) + (n-3) + ... + 0\\ &= 1 + 2 + ... + (n-1) \\ &= \sum_{k=1}^{n-1} k \\ &= \frac{n(n-1)}{2} \end{align*} $$

Problem 4: Simplify \(\displaystyle \sum_{k=0}^n 2^k\).

$$ \begin{align*} \sum_{k=0}^n 2^k &= 2^0 + 2^1 + 2^2 + ... + 2^n \\ &= 1 + 2 + 4 + ... + 2^n \\ &= \frac{2^{n+1} - 1}{2 - 1} \\ &= 2^{n+1} - 1 \end{align*} $$

Problem 5: Show that \(\displaystyle \sum_{k=1}^{\infty} \frac{1}{2^k}\) converges to 1.

$$ \begin{align*} \sum_{k=1}^{\infty} \frac{1}{2^k} &= \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \frac{1}{16} ...\\ &= \sum_{k=0}^{\infty} \frac{1}{2}\frac{1}{2^k}\\ &= \frac{1}{2} \sum_{k=0}^{\infty} \frac{1}{2^k}\\ &= \frac{1}{2} \cdot \frac{1}{1-\frac{1}{2}} \\ &= 1 \end{align*} $$