The main theorem: the problem when f (n) contains negative power log

Question

So, I calculated the average complexity of the case of the following function using the Wizard 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

Not applicable (non-polynomial difference between f (n) and n ^{log _b a} )

This answer also supports PDF by specifying NO.

However, in this video, the instructor solved the same question at 12:26, ​​he came out with the answer

 Θ(nloglogn) 

Can anyone explain which one is wrong and why ?

Answer 1

They are both right. The main theorem in PDF is not applied, but the instructor in the video uses an extended form of the main theorem that covers your case.

I could not find really good links to the version in the video, and this is not the version I found out, but there is evidence of it online here: http://homepages.math.uic.edu/~leon/cs-mcs401-s08/handouts /extended_master_theorem.pdf

Answer 2

As Matt Timmermans correctly points out, the statement does not follow from the main theorem, but it follows from the extended version.

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

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

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

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

• ...

• Level I has 2 nodes ⁱ each with a value of (n / 2 ⁱ ) / log (n / 2 ⁱ )

Simplification, level i introduces n / (log (n) - i).

Note that there are ~ log (n) - 1 levels to achieve the constant.

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

for k = log (n).

Note that the sigma is the kth harmonic row, which is & Theta; (log (k)) . The value k = log (n) gives generally n & Theta; (log (log (n))) = & Theta; (n log (log (n))).