Solving $T(n)=4T(n/4) +(n/\log n)^2$

Question

Solving $T(n)=4T(n/4) +(n/\log n)^2$.

When I looked at the question I thought that this can be solved by the 3rd case of the master theorem since $f(n)$ is polynomially larger than $n^{\log_ba }=n.$ But someone said that this is not polynomially larger since it has $(\log n)^2$ in the denominator.

Then I tried the substitution method. I have found an upper bound of $n^2$ and a lower bound of $n\log n$ but I am unable to proceed any further.

I want a theta bound.

Answer 1

Let $H (m) := T(4^m)$. The recurrence is now $H(m) = 4 H(m-1) + 16^{m} / 4m^2$.

By substituting, we get

$4H(m-1) = 16 H(m-2) + 4\cdot16^{m-1} / 4(m-1)^2$

$16H(m-2) = 64 H(m-3) + 16\cdot16^{m-2} / 4(m-2)^2$

$64H(m-3) = 256 H(m-4) + 64\cdot16^{m-3} / 4(m-3)^2$

...

That sequence ends with $4^mH(0)$. So we need to add $16^{m} / 4m^2$, $4\cdot16^{m-1} / 4(m-1)^2$, $16\cdot16^{m-2} / 4(m-2)^2$, $64\cdot16^{m-3} / 4(m-3)^2$, ..., $4^mH(0)$.

We extract a factor $16^{m} / 4$, then the numbers to add are $1 / m^2$, $1 / 4(m-1)^2$, $1 / 16(m-2)^2$, $1 / 64(m-2)^2$ etc. The sum is slightly larger than $16^m / 3m^2$. And T(n) is slightly larger than $(4/3)(n / log n)^2$.

Answer 2

Case 3 of the master theorem does apply here. Let me state case 3 in its Wikipedia form.

Consider a recurrence $$ T(n) = aT(n/b) + f(n). $$ Let $c^* = \log_b a$. Suppose that:

1. There exists $\epsilon > 0$ such that $f(n) = \Omega(n^{c^* + \epsilon})$.
2. There exist $N_0,k > 0$ such that $af(n/b) \leq kf(n)$ for all $n \geq N_0$.

Then $T(n) = \Theta(f(n))$.

In your case, $a=b=4$ and $f(n) = n^2/\log^2 n$. Since $a=b$, $c^* = 1$. Your function $f(n)$ satisfies $f(n) = \Omega(n^{1.5})$ (any number strictly between 1 and 2 would do here), and so satisfies the first condition with $\epsilon = 0.5$. As for the second condition, $$ af(n/b) = 4\frac{(n/4)^2}{(\log (n/4))^2} = \Theta\left(\frac{n^2}{\log^2 n}\right), $$ and in particular the second condition holds. The conclusion is that $T(n) = \Theta(f(n))$.

Answer 3

If you keep expanding using substitution, you'll sum the general term logn times. This will come out to be a geometric series and for a large n the sum directly tends to $4n^2/{3} [1-1/(4^{(\log n)^2))}]$ Which comes out to $n^2$ in terms of theta notation.

Working

General term:

$$ \frac {({\frac{n^2}{4^i}})}{(\log \frac{n} {4^i})} $$

This needs to be summed $k$ times, where $k$ is given by:

$$ \frac n {4^k} = 2$$ $k = \log n$

Sum this up $\log n$ times anad make some simple substitutions, you'll get $n^2.$ We can ignore the base case, because that'll simply contribute a term that will be lesser asympotitically than $n^2$