Lesson 7

A generalization of this theorem that allows for subproblems of different sizes is known as the Akra–Bazzi method. At the same time, the proof method for the above theorem can be easily extended to some such non-standard relations. For example, the order statistics algorithm known as the median of medians, introduced in 1973 by Blum, Floyd, Pratt, Rivest, and Tarjan (four of whom are Turing Award winners!), has the relation: \[T(n) \le T(n/5)+T(7n/10)+O(n) \ .\] This cannot be directly substituted into the above theorem. However, the same recursion tree can be drawn. Although it will not be as regular and balanced, its depth will still be \(O(\log n)\), and the work per level will decrease (like a geometric progression) due to the fact that \(1/5+7/10<1\). The total work can be estimated as \(T(n)=O(n)\).