0 votes 0 votes 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. Algorithms algorithms master-theorem + – sushmita asked Dec 4, 2016 sushmita 447 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.