The master theorem is a blight on the teaching of analysis of algorithms. The main reason is that few students understand what makes it work and end up treating it as a piece of plug-and-chug equipment. The second reason is that it is not very general.The alternative? Learn to love recursion trees. It addresses both issues. It's intuitive and it's general. As a side effect, the master theorem becomes an almost obvious fact; the three different cases correspond to geometric sums with increasing, decreasing and constant terms, with the caveat that since we are working asymptotically, increasing/decreasing/constant must be interpreted in the looser asymptotic sense. A geometric series with increasing (decreasing) terms is dominated by its last (first) term, corresponding in the recursion to the last (first) level of the tree. That makes it trivial to estimate the sum: just estimate the cost at the appropriate level and you're done. Only in the constant term case do all the terms play a role, but then you get your estimate by just multiplying the number of terms (the tree depth) by the constant value the terms have in common.

 All but the very simplest recursions require heavy machinery to find closed forms. If you can't apply the Master Theorem often your best bet is to guess the answer and try an induction, otherwise you quickly end up with generating functions and differential equations.

Applications are open for YC Winter 2022

Search: