So I was calculating average case complexity of the following function using Master's theorem:
T(n) = 2T (n/2)+ n/ log n
According to http://people.csail.mit.edu/thies/6.046-web/master.pdf Question 7,
It says
Does not apply (non-polynomial difference between f(n) and n log b a )
This answer also supports pdf, by saying NO.
However, in this video instructor has solved same question at 12:26, he came out with answer
Θ(nloglogn)
Can anyone explan which one is wrong and why?
They are both right. The Master Theorem in the PDF does not apply, but the instructor in the video is using an extended form of the master theorem that covers your case.
I wasn't able to find any really good references to the version in the video, and it's not the version I learned, but there is a proof of it online here: http://homepages.math.uic.edu/~leon/cs-mcs401-s08/handouts/extended_master_theorem.pdf