Master theorem: issue when f(n) contains negative power of log

Question

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?

Drysalt

Answer 1

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

Mcphail

After having a look at all of them, I gues only difference is when negative power is equal to -1. if it is less then even -1, it falls into case 1 as it is asymtotically less than n ^ (log a base b) – Drysalt

Answer 2

As Matt Timmermans correctly notes, the statement doesn't follow from the master theorem, but it does follow from an extended version of it.

It's quite simple to solve this problem directly using the tree method.

Starting with T(n) = 2T (n/2)+ n / log n:

• Level 0 has 1 node with value n / log(n).

• Level 1 has 2 nodes, each with value (n / 2) / log(n / 2).

• ...

• Level i has 2ⁱ nodes, each with value (n / 2ⁱ) / log(n / 2ⁱ)

Simplifying, level i contributes n / (log(n) - i).

Note that, altogether, there are ~log(n) - 1 levels to reach a constant.

Consequently, the sum of all levels is ∑_{i = 0}^{~log(n) - 1}[n / (log(n) - i)] ~ n ∑_{i = 0}^k[1 / k],

for k = log(n).

Note that the sigma is the kth harmonic series, which is Θ(log(k)). Setting k = log(n) gives altogether n Θ(log(log(n))) = Θ(n log(log(n))).

Cumulous