How to solve this recurrence function with substition method?-CodePudding

I have a very strange function which looks like this:

T(n) = 2T(n/2) n* log2(n)

I need to solve this with the substitution method, but I haven't been able to reach any decisive answer.

I need solution steps and big-O

CodePudding user response：

When facing log, change like n = 2^k (k = log2(n)) is often a way out:

n = 2^k

So we have

T(2^k) = 2 * T(2^(k - 1))   k * 2^k

Let's see what does it mean:

T(2^k) = 2 * T(2^(k - 1))   k * 2^k =
       = 2 * (2 * T(2^(k - 2))   (k - 1) * 2^(k - 1))   k * 2^k =
       = 4 * T(2^(k - 2))   (k - 1) * 2^k   k * 2^k =
       = 4 * (2 * T(2^(k - 3))   (k - 2) * 2^(k - 2))   (k - 1) * 2^k   k * 2^k = 
       = 8 * T(2^(k - 3))   (k - 2) * 2^k   (k - 1) * 2^k   k * 2^k = 
         ...
       = 2^k * T(0)   2^k   2 * 2^k   ...   k * 2^k =
       = 2^k * T(0)   2^k (1   2   ...   k) =
       = 2^k * T(0)   2^k * k * (k   1) / 2 =
       = 2^k * (T(0)   k * (k   1) / 2)

Time to return to n, n = log2(k):

T(n) = n * (T(0)   log2(n) * (log2(n)   1) / 2)

In term of O(n) we have

O(T(n)) = O(n * (T(0)   log2(n) * (log2(n)   1) / 2)) =
        = O(n * (const   log2(n)^2 / 2   log2(n) / 2) =
        = O(n * log2(n)^2 / 2) =
        = O(n * log2(n)^2) =
        = O(n * log(n)^2)

So, the answer is

O(T(n)) = O(n * log(n)^2)

Note, that since log2(n) == log(n, b) / log(2, b) for arbitrary base b > 1 we can use log(n) instead of log2(n)