A frame for general divide-and-conquer recurrences

作者：Wang XD^*; Fu QX

来源：Information Processing Letters, 1996, 59(1): 45-51.

DOI：10.1016/0020-0190(96)00076-2

• divide-and-conquer
• algorithms
• recurrence
• time complexity

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.

• 出版日期1996-7-8
• 单位福州大学