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 link https://www.youtube.com/watch?v=lPUhHmgrpik instructor has solved same question at 12:26, he came out with answer
Θ(nloglogn)
He has used extended masters theorem.
This is the link to extended masters theorem- http://homepages.math.uic.edu/~leon/cs-mcs401-s08/handouts/extended_master_theorem.pdf
Now which concept to follow in gate??
please any expert check this.
64.3k questions
77.9k answers
243k comments
79.7k users