MATH 302 Lecture 17

« previous | Wednesday, October 26, 2011 | next »

Chapter 8.3: Divide and Conquer Algorithms

Examples:

• Binary Search on Sorted List: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n) = f\left(\frac{n}{2}\right) + 2}
• Merge Sort: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n) = 2 f \left( \frac{n}{2} \right) + n}
• Recursive Max/Min of Unsorted List: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n) = 2 f \left( \frac{n}{2} \right) + 2}
• Multiplying 2n-bit Numbers: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(2n) = 3f(n) + c(n)}

In general, form is:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n) = a f \left( \frac{n}{b} \right) + g(n) }

Note: the book restricts the last term to powers of n

Master Theorem

The master theorem provides a general boilerplate solution for solving recurrence relations (like divide and conquer algorithms) that satisfy a particular format.

Definition

Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} be an increasing function satisfying a recurrence relation:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(n) = af\left(\frac{n}{b}\right) + cn^d}

Whenever

• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=b^k} for some $k\geq 1$, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \ge 1}
• $b$ is an integer > 1
• $c$ and $d$ are real numbers ≥ 0

Then

$f(n)=af\left({\frac {n}{b}}\right)+cn^{d}={\begin{cases}\Theta \left(n^{d}\right)&a<b^{d}\\\Theta \left(n^{d}\log {n}\right)&a=b^{d}\\\Theta \left(n^{\log _{b}{a}}\right)&a>b^{d}\end{cases}}$

Proof

Proposition. If $a=b^{d}$ and $n$ is a power of $b$, then a function $f$ satisfying the recurrence relation $f(n)=af(n/b)+cn^{d}$ is of the form $f(n)=f(1)n^{d}+cn^{d}\log _{b}{n}$

Proof. Let $k=\log _{b}{n}$. Then

${\begin{aligned}f(n)&=cn^{d}+ac\left({\frac {n}{b}}\right)^{d}+a^{2}c\left({\frac {n}{b^{2}}}\right)^{d}+\dots +a^{k-1}c\left({\frac {n}{b^{k-1}}}\right)^{d}+a^{k}f(1)\\&=a^{k}f(1)+\sum _{j=0}^{k-1}a^{j}c\left({\frac {n}{b^{j}}}\right)^{d}\\&=a^{k}f(1)+\sum _{j=0}^{k-1}cn^{d}\\&=a^{k}f(1)+kcn^{d}\\&=a^{\log _{b}{n}}f(1)+c(\log _{b}{n})n^{d}\\&=b^{d\log _{b}{n}}f(1)+c(\log _{b}{n})n^{d}\\&=n^{d}f(1)+c(\log _{b}{n})n^{d}\\&=O(n^{d}\log {n})\end{aligned}}$

Counting

Product Rule

Suppose we have to make $n_{1}$ choices followed by $n_{2}$ choices. For example, selecting what to wear from $n_{1}$ shirts and $n_{2}$ pants. For each shirt you choose, there are $n_{2}$ possible pants to choose from. Therefore, the total number of choices is their product: $n_{1}n_{2}$

Addition Rule

When choices are independently selected. For example, when choosing a representative for a high school: there are $n_{1}$ freshmen, $n_{2}$ sophomores, $n_{3}$ juniors, and $n_{4}$ seniors. There are $\sum _{i=1}^{4}n_{i}$ ways to choose a representative among all high school students.

Inclusion-Exclusion

Just like in statistics:

$\left|A\cup B\right|=\left|A\right|+\left|B\right|-\left|A\cap B\right|$

For example: How many bit strings of length $n$ either begin with 1 or end with 00?

• There are $2^{n-1}$ bit strings that begin with 1
• There are $2^{n-2}$ bit strings that end with 00
• There are $2^{n-3}$ bit strings thta begin with 1 and end with 00

Therefore, there are $2^{n-1}+2^{n-2}-2^{n-3}$ bit strings that begin with 1 or end with 00.

Division Rule

How many 3-item subsets can be made from a set of $n$ elements?

There are $n$ ways to choose the first element, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n-1} ways to choose the second element, and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n-2} ways to choose the last element. Since the three elements can be rearranged in 3! = 6 ways, and inclusion in a set does not rely on the order, we divide the total number of ways to choose the set by 6:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{n(n-1)(n-2)}{3}= \binom{n}{3}}

Counting Functions

How many functions are there from {a, b, c, d} to {1, 2, 3}?

For each element in the domain (a, b, c, and d), there are 3 targets to choose from in the codomain. Therefore, the number of possible functions is 3 · 3 · 3 · 3 = 3⁴

In general, for a domain containing Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} items and a codomain containing Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c} items, the number of possible functions from the domain to the codomain is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c^d}

One-to-One Functions

For a one-to-one function, once an element in the codomain has been chosen, it cannot be pointed to by any element in the domain. Therefore, the number of possible one-to-one functions is <math>c(c-1)(c-2)\dots(c-d+1) = \frac{c!}{(c-d)!}