 This recurrence has solution formula_46.It follows that there is a positive constant formula_47 such that a problem of size at most formula_48 fits entirely in cache, meaning that it incurs no additional cache misses.Letting formula_49 denote the number of cache misses incurred by a call to a k-merger, one can show that formula_50 This is done by an induction argument.