Search code examples
algorithmmathdivide-and-conquermaster-theorem

Calculate the recurrence use repeated unfolding

I am trying to calculate T (n) = 2 T (n/2) + n (log n)^2. Following the step I got:

=2^kT(n/2^k)+ nlog2 (n/2^(k-1))+ nlog2 (n/2^(k-2))+…+ n(log (n/2))^2 + n (log2 n)^2

when n=2^k I got:

formula

But I have no idea about how to simplify the summation formula and get Θ() notation. Any one can help? Thanks a lot

Solution

  • The summation you have doesn't look quite right to me. Let's re-derive it:

    enter image description here

    ... after m iterations. Let's assume the stopping condition is n = 1 (without loss of generality):

    enter image description here

    ... where we have employed two of the logarithm rules. As you can see the summation is in fact over "free indices" and not the logs themselves. Using the following integer power sums:

    enter image description here

    ... we get:

    enter image description here

    To evaluate the Θ-notation, the highest order term is:

    enter image description here