**Integer Multiplication**

Given two numbers and compute . The algorithm we learned at school where we compute as takes .

**First divide and conquer attempt**: Let us consider a naive divide and conquer approach by writing and . Then . If is the time to multiply two digit numbers, then the recurrence relation is . This implies that 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 digit numbers in order to solve the problem. Notice that . Thus computing , and suffices to compute . The recurrence relation now becomes . This gives a running time of which is roughly since .

**Master Theorem**

Suppose we have a recurrence relation of the form . We have the following three cases:

- if
- if
- if

**k-Select**

Given a list of non-negative integers we want to find the largest element. If then a trivial algorithm where we find the element takes time. Suppose then an obvious approach would be to sort the array and return the entry. This takes 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 and as in quicksort, where then we would be done, since where . The largest element in the whole list is then either the largest element in the list of size or the largest element in the list of size .

http://web.mit.edu/~neboat/www/6.046-fa09/rec1.pdf

Master Theorem practice problems with solutions

http://people.csail.mit.edu/thies/6.046-web/recitation2.pdf

An intuitive explanation of how to apply the master theorem