Solve the recurrence: T(n)=2T(n/2)+n/logn

Question

I can find the sum of each row (n/log n-i) and also I can draw its recursive tree but I can't calculate sum of its rows.

T(n)=2T(n/2)+n/logn

T(1) = 1

Edna

Answer 1

Suppose n = 2^k;

We know for harmonic series (euler formula):

Sum[i = 1 to n](1/i) ~= log(n) [n -> infinity]

t(n) = 2t(n/2) + n/log(n)
     = 2(2t(n/4) + n/2/log(n/2)) + n/log(n)
     = 4t(n/4) + n/log(n/2) + n/log(n)
     = 4(2t(n/8) + n/4/log(n/4)) + n/log(n/2) + n/log(n)
     = 8t(n/8) + n/log(n/4) + n/log(n/2) + n/log(n)
     = 16t(n/16) + n/log(n/8) + n/log(n/4) + n/log(n/2) + n/log(n)
     = n * t(1) + n/log(2) + n/log(4) + ... + n/log(n/2) + n/log(n)
     = n(1 + Sum[i = 1 to log(n)](1/log(2^i)))
     = n(1 + Sum[i = 1 to log(n)](1/i))
     ~= n(1 + log(log(n)))
     = n + n*log(log(n)))
     ~= n*log(log(n)) [n -> infinity]

Coppage

Answer 2

When you start unrolling the recursion, you will get:

Your base case is T(1) = 1, so this means that n = 2^k. Substituting you will get:

The second sum behaves the same as harmonic series and therefore can be approximated as log(k). Now that k = log(n) the resulting answer is:

Noncompliance

Sorry for asking in such an old post, but I was looking to your answer and i've been trying to understand why the sum from i=0 to k-1 {1/(k-i)} behaves the same as harmonic series. Thank you in advance. – Masturbate

@Ph. just write the sum as the actual summation of k-1 elements and it will be obvious. – Noncompliance

can you show the solution by using substitution method ? – Defelice

Answer 3

Follow Extended Masters Theorem Below.

Using Extended Masters Theorem T(n)=2T(n/2)+n/logn can be solved easily as follows. Here n/log n part can be rewritten as n * (logn)^-1, Effictively maaking value of p=-1. Now Extended Masters Theorem can be applied easily, it will relate to case 2b of Extended Masters Theorem .

T(n)= O(nloglogn)

Follow this for more detailed explanation

https://www.youtube.com/watch?v=Aude2ZqQjUI

Bout