Lesson 1

Some computational problems are solved using the divide-and-conquer method as follows: a problem of size \(n\) is divided into \(a\) subproblems of size \(n/b\), which are solved recursively, and their solutions are then combined to obtain the solution to the original subproblem. If the algorithm spends \(O(n^{d})\) time outside the recursive calls (this includes constructing subproblems and processing their solutions), then the runtime \(T(n)\) of this algorithm satisfies the following relation: \[T(n)=aT(n/b)+O(n^{d}) \ .\] Here are some examples of such recurrence relations:

• Binary search in a sorted sequence: \[T(n) = T(n/2)+O(1) \ .\]


• Many sorting algorithms, as well as the Fast Fourier Transform algorithm (used for polynomial multiplication): \[T(n) = 2T(n/2)+O(n)\ .\]


• Karatsuba's algorithm for multiplying numbers: \[T(n) = 3T(n/2)+O(n) \ \]


• Strassen's algorithm for matrix multiplication: \[T(n) =7T(n/2)+O(n^{2}) \ .\]