In Beyond Cracking the Coding Interview, we give a simple method for analyzing recursive functions (especially backtracking): the BAD method.

The runtime of a recursive function is O(b^d * A), where:

- b is the maximum branching factor of the call tree. It must be ≥ 2.
- d is the depth of the call tree.
- A is the additional work (not counting recursion) at any particular node in the call tree.

We call it 'BAD' to reminds us of the 3 variables in the analysis, but also because it can be "bad" in that it gives us a valid upper bound, but it is not necessarily tight.

For instance, for merge sort, the BAD method gives us a runtime of O(n^2).

Here's the practical advice: for famous algorithms like merge sort and quicksort, memorize the runtime. For anything else, there's the BAD method.