CSCE 222 Lecture 25

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

Divide and Conquer

Example

Multiplication of Integers

In binary form, two number $a$ and $b$ consist of $2n$ bits. Each integer can be rewritten as a sum of two $n$-bit integers that represent the most and least significant bits.

$\begin{array}{rl}a& =(a_{2n-1},a_{2n-2},\dots ,a_1,a_0)\\ & =2^n{A}_1+A_0=(a_{2n-1},\dots ,a_n)+(a_{n-1},\dots ,a_0)\\ b& =(b_{2n-1},b_{2n-2},\dots ,b_1,b_0)\\ & =2^n{B}_1+B_0=(b_{2n-1},\dots ,b_n)+(b_{n-1},\dots ,b_0)\\ 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{array}$

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)+c{n}^d$

Whenever

• $n=b^k$ for some $k\ge 1$, $a\ge 1$
• $b$ is an integer > 1
• $c$ and $d$ are real numbers ≥ 0

Then

$f(n)=af\left(\frac{n}{b}\right)+c{n}^d=\{\begin{array}{ll}O\left(n^d\right)& a<b^d\\ O(n^d\log n)& a=b^d\\ O\left(n^{{\log }_{b}a}\right)& a>b^d\end{array}$

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)+c{n}^d$ is of the form $f(n)=f(1)n^d+c{n}^d{\log }_{b}n$

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

$\begin{array}{rl}f(n)& =c{n}^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}c{n}^d\\ & =a^{k}f(1)+kc{n}^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{array}$