algorithmcomplexity-theorymaster-theorem

Master Theorem with function nlogn

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.

Solution

  • 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;