Jan 14. Integer multiplication, Master theorem, k-select

Integer Multiplication

Given two numbers $A = a_n a_{n-1} \ldots a_1$ and $B = b_n b_{n-1} \ldots b_1$ compute $AB$. The algorithm we learned at school where we compute $AB$ as $b_1A + 10 b_2 A + \ldots 10^{n-1} b_n A$ takes $\Theta(n^2)$.

First divide and conquer attempt: Let us consider a  naive divide and conquer approach by writing $A = 10^{n/2} A_2 + A_1$ and $B = 10^{n/2} B_2 + B_1$. Then $AB = 10^n A_2 B_2 + 10^{n/2} (A_1 B_2 + A_2 B_1) + A_1 B_1$. If $T(n)$ is the time to multiply two $n$ digit numbers, then the recurrence relation is $T(n) = 4 T(n/2) + O(n)$. This implies that $T(n) = \Theta(n^2)$ and so asymptotically it is no better than the previous algorithm.

Second divide and conquer attempt: We observe that one does not need to multiply four $n/2$ digit numbers in order to solve the problem. Notice that $(A_1 + A_2)(B_1 + B_2) = A_1B_1 + (A_2B_1 + A_1 B_2) + A_2B_2$. Thus computing $A_1B_1$, $A_2 B_2$ and $(A_1 + A_2)(B_1 + B_2)$ suffices to compute $AB$. The recurrence relation now becomes $T(n) = 3 T(n/2) + O(n)$. This gives a running time of $T(n) = \Theta(n^{\log_2 3})$ which is roughly $\Theta(n^{1.58})$ since $\log_2 3 \approx 1.58$.

Master Theorem

Suppose we have a recurrence relation of the form $T(n) = a T(n/b) + O(n^d)$. We have the following three cases:

1. $T(n) = \Theta(n^d)$ if $a < b^d$
2. $T(n) = \Theta(n^d \log_b n)$ if $a=b^d$
3. $T(n) = \Theta(n^{\log_b a})$ if $a > b^d$

k-Select

Given a list of non-negative integers $a_1, a_2, \ldots, a_n$ we want to find the $k^{th}$ largest element. If $k=O(1)$ then a trivial algorithm where we find the $1^{st}, 2^{nd}, \ldots, k^{th}$ element takes $O(n)$ time. Suppose $k = \Omega(1)$ then an obvious approach would be to sort the array and return the $k^{th}$ entry. This takes $\Theta(n\log n)$ time. Can we do it faster?

Preliminary idea: If we could find a pivot element such that the list is split into two parts of size $c_1 n$ and $c_2 n$ as in quicksort, where $c_1,c_2 < 1$ then we would be done, since $T(n) = T(c n) + O(n)$ where $c = \max \{c_1, c_2\} < 1$. The $k^{th}$ largest element in the whole list is then either the $k^{th}$ largest element in the list of size $c_1 n$ or the $(k-c_1n)^{th}$ largest element in the list of size $c_2n$.