Question

Solve this recurrence relation: T(n) = T(n/2) + n/log n

Answer 1

Using masters theorem:

a = 1, b = 2

n^lg1 = n^0 = 1 < n/logn

∴T(n) = theta( n/logn)

Comments

Professor, Can we apply masters theorem for this question ?

Answer 2

We have T(n) = T(n/2) + n/log n

so if we expand we get T(n) = T(n/2^k) + n/log n + [(n/2)/log (n/2) + ..... (n/2^(k-1) /log (n/2^(k-1))]  .

We assume T(1) = 1 => n/2^k = 1.   => k = log n;

so we get T(n) = 1+(2/1)+(4/2)+(8/3)+....(2^k/k) [ where k = log n ]

so we get range for T(n) ,

we know that 2+4+8+...2^k = 2*(2^k  - 1)  = 2*(n-1);

 T(n)  >  1 + 1/k(2+4+....2^k) which is O(n/logn)

T(n) < 1+ (2+4+...2^k) which is O(n) .

So it lies in between the above two calculated values .

Answer 3

T(n) = T(n/2) + n * (log n) ^-1

Using the Master Theorem,

a= 1, b = 2, K = 1, P = -1

log2 1=0  <  K=1

Since, P<0 

∴ T(n) = Theta(n).

Answer 4

To solve this problem we need to use advanced Masters theorem:

Since in normal Masters theorem f(n) = n / logn is not defined ( P = -1, where P is the power of log)

So, A = 1, B = 2, K = 1(power of N) and P = -1

log 2 (1) = 0   which is less than K = 1 ( third case)

When P = -1, T(n) = Theta(n)