Search code examples
algorithmtime-complexityasymptotic-complexityclrs

Applying Case 3 Of The Master Theorem

Introduction to Algorithms CLRS 4.3 (b) has the problem

T(n) = 3*T(n/3) + n/lg(n)

Note that n^(log a/ log b) = n^(log 3/ log 3) = 1

The book states that here the master theorem case 3 cannot be applied since n/log (n) is not polynomially larger i.e. it is asymptotically less than n^(k) where k is any positive constant.

My question is: Let's take k = 0.1 then n/log (n) is always asymptotically greater than n^(0.1), but this is contradicting the above statement. What am I doing wrong?

Solution

  • IIUC, you have a mistake in applying the antecedent of case 3.

    Your recurrence is

    T(n) = 3 T(n/3) + n/lg(n)

    which, in the conventions of the Master Theorem means that a = b = 3

    For the third case, you must have n / log(n) = Ω(nc), where c > log3(3) = 1. This indeed does not apply here.