A frame for general divide-and-conquer recurrences

The time complexities of general divide-and-conquer algorithms can often be analysed by solving the recurrence equations in the form T(n) = a(n)T(b(n)) + f(n). Much work has been done for solving recurrences of this form. The only methods presented previously, however, consist of solution tables for fixed a(n), b(n) and f(n). A systematic way of solving general recurrences of the above form is not available so far. We present a general frame for solving recurrences of the above form.