Posted by: atri | November 9, 2011

## Lect 30: Multiplication Algorithm

We studied the $O(n^{\log_2{3}})$ time algorithm to multiply two \$n\$-bit integers. I forgot to mention this in class– the algorithm is due to Karatsuba. The Wikipedia page on the algorithm has the interesting history on how the algorithm was discovered. We then started with the problem of counting the number of inversions, which we will continue on Friday. The material will be from Sec 5.3 in the textbook.