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.

Advertisements

2 Comments

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s