Master theorem

Question

T(n)=3T(n/4)+nlogn

In this if we use master theorem then how is f(n)=Ω(nlog43+ϵ) ?

Comments

here n^log_ba = n^0.7 some thing which is less than nlogn but important thing is n^0.7 < n¹ itself so oviously less than nogn . so master theorm aplly here answer would be nlogn .

---

but isn't it logarithmic times smaller?

---

since  n^0.7 < n¹  right na?

---

i get it. Thanks! :)

Answer 1

The reason is clearly stated in CLRS as :

if f(n) is larger than n^log_ba than it should be polynomially larger, this means that there must always be a factor of n^ϵ, where ϵ>0, in f(n) and not some smaller factor like logn.

Factors llike logn is asymptotically less than n^ϵ for any positive ϵ, so if these factors are present standalone then it doesn't satisfy the case 3 condition for master theorem. There must always be a factor n^ϵ more than n^log_ba in f(n) for case 3 to be satisfied.