Master theorem: issue when f(n) contains negative power of log
<p>So I was calculating average case complexity of the following function using Master's theorem:</p>

<pre><code>T(n) = 2T (n/2)+ n/ log n
</code></pre>

<p>According to <a href="http://people.csail.mit.edu/thies/6.046-web/master.pdf" rel="noreferrer">http://people.csail.mit.edu/thies/6.046-web/master.pdf</a> Question 7,</p>

<p>It says</p>

<p><em>Does not apply (non-polynomial difference between f(n) and n <sup>log <sub>b</sub> a </sup>)</em></p>

<p><a href="https://stackoverflow.com/questions/28093121/difference-between-solving-tn-2tn-2-n-log-n-and-tn-4tn-2-n-log-n">This answer</a> also supports pdf, by saying NO.</p>

<p>However, in <a href="https://youtu.be/lPUhHmgrpik?t=746" rel="noreferrer">this video</a> instructor has solved same question at 12:26, he came out with answer</p>

<pre><code>Θ(nloglogn) 
</code></pre>

<p>Can anyone explan which one is <strong>wrong</strong> and <strong>why</strong>?</p>