CODEWITHSUNDEEP
algorithmtime-complexityasymptotic-complexityclrs
Himanshu Ahuja
Himanshu Ahuja

Reputation: 37

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?

Upvotes: 2

Views: 744

Answers (1)

Ami Tavory
Ami Tavory

Reputation: 76297

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.

Upvotes: 1

Related Questions