Master Theorem with function nlogn

1
votes

We recently got tasks in my study to solve the complexity of recursive functions with the master theorem. I am aware that those questions have been asked a lot here, but I can't figure out the answer to this question from those. One question, in particular, describes the problem well: here

My problem is for the recursive function T(n) = 5*T(n/3) + n *log(n). As stated in the other question, this should be solvable with the second case (or the unofficial fourth case, those a pretty similar). However, I can't find a Big-Theta of f(n) = nlogn with a =5 and b = 3.

I would appreciate your help.

1
algorithmcomplexity-theorymaster-theorem
Seems to me you can apply case 1 (i.e. f(n) = O(n^c) where c < ccrit). - Henry
The definitions in that question (not its accepted answer) are dubious (they are all the exact same case). Use the definition from a more reputable source instead (e.g. Wikipedia). - meowgoesthedog
(geeksforgeeks.org/…) This link will be helpful to you. It is an based on advanced version of master's theorem - sahushivam

1 Answers

2
votes

The problem can be solved with the Master theorem if we can show that f(n) = n log n = O(n^(log_3 5-\epsilon))

if holds then the result follows from the first case of the Master Theorem

T(n) = Θ(n^(log_3 5))

To see that;

  • take lim (n log n)/n^(log_3 5))
  • evaluate log_3 5 ~ = 1.4649..
  • substruct some epsilon = 0.0049...>0,
  • lim (n log n)/n^(1.46)
  • cancel n's
  • limit log n / n^(0.45) = 0 and take the first H'ospital
  • limit n^(0.54)/(n * 0.46) =0