Multiplication

Grade School Algorithmic Problem:

Given two n-digit numbers $x, y$ , output $x \cdot y$

size of instance: n

n - 1 additions of O(n)-digit numbers, resulting in…

Total number of basic operations:

T (n) = O (n^{2})

Is there a faster way?

Half instance sizes (each var of $n /2$ ) (naive approach):

x = x_{L} x_{R}

y = y_{L} y_{R}

Recursive Multiplication:

mult(x, y) if n = 1, output x * y else return $1 0^{n} * m u lt (x_{L}, y_{L}) + 1 0^{\frac{n}{2}} (m u lt (x_{L}, y_{R}) + m u lt (x_{R}, y_{L})) + m u lt (x_{R}, y_{R})$

Running time? Recursive relation:

T (n) = 4 \cdot T (n /2) + O (n)

Explanation: 4 subproblems of size n/2 then combining with addition of O(n)-digit numbers, which takes O(n) time. Why?

New idea:

Identity:

x_{L} y_{R} + x_{R} y_{L} = (x_{L} + x_{R}) (y_{L} + y_{R}) - x_{L} y_{L} - x_{R} y_{R}

Plug back in for new recursive formula: (computes using already known values)

mult2(x, y)
	if n = 1, return x * y
	else
		p1 = mult2(x_left, y_left)
		p2 = mult2(x_right, y_right)
		p3 = mult2(x_left + x_right,y_left + y_right)
		return p1 * 2^n + (p3 - p1 - p2) * 2^(n/2) + p2

Running time?

T (n) = O (n^{l o g_{2} 3}))

T (n) = 3 T (n /2) + O (n)

Solving recurrence relations:

General set-up:

to solve a problem of size n, we need $a$ subproblems of size $n / b$ and $O (n^{d})$ recombination time.
$a, b, d$ parameters
mult: $a = 4, b = 2, d = 1$
mult2: $a = 3, b = 2, d = 1$

General recurrence:

T (n) = a T (n / b) + O (n^{d})

mult2: 3 subproblems of n/2 and an $O (n)$ recombination time

forms a tree

Tree definition:

depth: $d e pt h = l o g_{b} n$
recombination time for a single problem at level j: $O ((\frac{n}{b ^{d}})^{d})$
num nodes at level j: $a^{j}$
time spent at level j: $a^{j} (\frac{n}{b ^{j}})^{d} = n^{d} (\frac{a}{b ^{d}})^{j}$
- e.g. for mult2, $= n (3/2)^{j}$

Master Theorem

In general: 3 cases

$a > b^{d}$ , $T (n) = O (n^{l o g_{b} a})$ - bottom level dominates (work grows at each level)
$a < b^{d}$ , $T (n) = O (n^{d})$ - top heavy (work shrinks at each level)
$a = b^{d}, T (n) = O (n^{d} l o g n)$ - work is equal at every level

3 says every level takes the same computation

$a$ - subproblem count $b$ - division of n $d$ - degree of recombination time

First example:

Binary search:

T (n) = T (n /2) + O (1)

a = 1, b = 2, d = 0

a = b^{d}

Matches the third case:

T (n) = O (l o g n)

Second example: Merge Sort

lecture notes: https://static.us.edusercontent.com/files/dVKhl6iQpQcVo0YrCFdpBak5

Intuition for getting Big O from Recursion Trees

Three general cases Goal is to determine which one an algorithm falls into

Top-heavy

The work done at the top is the biggest This could happen when $T (n) = 4 T (n /2) + O (n)$ where $a > b^{d}$

Balanced

The work is done equally throughout

Example

$T (n) = 2 T (n /2) + O (n)$ where $a = b^{d}$ Evaluated with recursion trees like 2(n/2) = n which is the same work as the top level

Big O

$O (n^{d} l o g_{b} a)$

kjk81's garden

Explorer

3. Divide and Conquer