Question

2. To calculate the computational complexity — a measure for the maximal possible number of steps needed in a computation — of the ‘mergesort’ algorithm (an algorithm for sorting natural numbers in non-decreasing order) one can proceed by solving the following recurrence relation:

$ZP1MIzsHgAAAABJRU5ErkJggg==$

(a) Use the method of generating functions to solve this recurrence relation.

(b) The relation between the number tm of computations needed to sort m numbers, and the solution am of the recurrence relation, is given by t2m = am . Use this to find an expression for tn , where n = 2m (or log2 n = m ), explicitly as a function of n , and conclude that tn ∼ n log2 n for large n . 0 1 0 1 R 2 0 L 5 1 0 R 0 1 R 1 2 1 R 4 1 R 5 3 0 R 1 1 L 3 4 1 L 3 1 L 5

Answer 1

Given that, The recurrence is, a_n = 2 a_n - 1 + 2 - 1, with a_0 = 0 Let the generating function g(x). g(x) = sigma_n greaterthanorequalto 0 a_n x^n we have, a_n = 2 a_n -1 + 2 - 1 a_n - 2 a_n - 1 = 2 - 1 multiplying by x^n and sum sigma_n greaterthanorequalto 0 a_n x^n - sigma_n greaterthanorequalto 0 2 a_n - 1 x^n = sigma_n greaterthanorequalto 0 2^n x^n - sigma_n greaterthanorequalto 0 x^n g(x) - a_0 - 2 x g(x) = 2x/1 - 2x - x/1 - x g(x) - 0 - 2x g(x) = 2x/1 - 2x - x/1 - x (1 - 2x)g(x) = 2x/1 - 2x - x/1 - x (1 - 2x)g(x) = 2x(1 - x) - x(1 - 2x)/(1 - 2x)(1 - x) g(x) = x/(1 - x)(1 - 2x)^2 on Comparison with \r\n A/1 - 2x + B/(1 - 2x)^2 + C/1 - x = x/(1 - 2x)^2(1 - x) A(1 - 2x)(1 - x) + B(1 - x) + C(1 - 2x)^2 = x put x = 1/2 then B = 1 Put