CSCE 222 Lecture 25

« previous | Wednesday, April 6, 2011 | next »

Divide and Conquer

Example

Multiplication of Integers

In binary form, two number 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} 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 b} consist of 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 2n} bits. Each integer can be rewritten as a sum of two 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} -bit integers that represent the most and least significant bits.

${\begin{aligned}a&=\left(a_{2n-1},\ a_{2n-2},\ \ldots ,\ a_{1},\ a_{0}\right)\\&=2^{n}A_{1}+A_{0}=\left(a_{2n-1},\ \ldots ,\ a_{n}\right)+\left(a_{n-1},\ \ldots ,\ a_{0}\right)\\b&=\left(b_{2n-1},\ b_{2n-2},\ \ldots ,\ b_{1},\ b_{0}\right)\\&=2^{n}B_{1}+B_{0}=\left(b_{2n-1},\ \ldots ,\ b_{n}\right)+\left(b_{n-1},\ \ldots ,\ b_{0}\right)\\ab&=(2^{n}A_{1}+A_{0})(2^{n}B_{1}+B_{0})=(2^{2n}+2^{n})A_{1}B_{1}+2^{n}(A_{1}-A_{0})(B_{0}-B_{1})+(2^{n}+1)A_{0}B_{0}\end{aligned}}$

Let $f(n)$ be the total number of bit operations needed to multiply two $n$-bit integers. In this case, $f(2n)=3f(n)+Cn$.

Bitwise Shift Operator

a >> n shifts the binary digits of $a$ $n$ places to the right (essentially multiplying $a$ by $2^{n}$).

Master Theorem

Let $f$ be an increasing function satisfying a recurrence relation:

$f(n)=af\left({\frac {n}{b}}\right)+cn^{d}$

Whenever

• $n=b^{k}$ for some $k\geq 1$, $a\geq 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}O\left(n^{d}\right)&a<b^{d}\\O\left(n^{d}\log {n}\right)&a=b^{d}\\O\left(n^{\log _{b}{a}}\right)&a>b^{d}\end{cases}}$

Proof

Proposition. If $a=b^{d}$ 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} is a power of 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 b} , then a function 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} satisfying the 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(n/b) + cn^d} is of the form 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(1)n^d+cn^d\log_b{n}}

Proof. 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 k = \log_b{n}} . Then

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 \begin{align} f(n) &= cn^d + ac\left(\frac{n}{b}\right)^d+a^2c\left(\frac{n}{b^2}\right)^d+\dots+a^{k-1}c\left(\frac{n}{b^{k-1}}\right)^d+a^kf(1) \\ &= a^k f(1) + \sum_{j=0}^{k-1} a^jc\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{align}}