in Algorithms
424 views
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.

in Algorithms
424 views

Please log in or register to answer this question.

Related questions