In a 1994 paper, Flajolet and Golin analyzed the mergesort recurrences by using tools from analytic number theory. I try to extend the mergesort recurrence to a multidimensional setting, solving multidimensional divide-and-conquer recurrences of the form ^k-1 _m=0^{k-2 m} _m^k _{k m}^k...[ Read more ]

In a 1994 paper, Flajolet and Golin analyzed the mergesort recurrences by using tools from analytic number theory. I try to extend the mergesort recurrence to a multidimensional setting, solving multidimensional divide-and-conquer recurrences of the form

T(n,k) = T(⌈n/2⌉, k) + T(⌊n/2⌋, k) + T(n, k - 1) + ⊝(n)

exactly which were previously only analyzed using combinatorial techniques.

A major advantage of my results is that the combinatorial techniques were only able to derive first-order asymptotics. The techniques that are used in this thesis permit deriving full closed-form formula:

T(n,k)= n lg^k-1 n / (k-1)! = n∑_m=0^k-2[lg^m n A_m^k(lg n)] - c_k

where A_m^k is some periodic functions with period 1. This is done by using the Mellin-Perron formula in Mellin transform analysis to study the Dirichlet generating function of the recurrence, which transforms the original problem of recurrence into an integral that is evaluated by the Cauchy's residue theorem in this thesis.