I have a question related to algorithm time complexity and master theorem.
How to solve this master theorem $T(n) = 2T(n/2) + n\cdot \log(\log(n))$?
We have 3 cases:
I don't know which one to use and why.
algorithmscomputational complexityrecurrence-relations
I have a question related to algorithm time complexity and master theorem.
How to solve this master theorem $T(n) = 2T(n/2) + n\cdot \log(\log(n))$?
We have 3 cases:
I don't know which one to use and why.
Best Answer
This relation can not be used with the Master Theorem because $f(n)=n\log \log n$ does not meet any of the cases.
This isn't really a rigorous proof, but that's the logic behind why the Master Theorem doesn't apply here. In general, the Master Theorem only applies to polynomials or polylogarithmic complexities and $n\cdot\log\log n$ are neither of those.