1
$\begingroup$

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.

Improve this question
$\endgroup$
2
1
$\begingroup$

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$.

Improve this answer
$\endgroup$
1
$\begingroup$

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))$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Yuval please add your original answer to this answer. That answer had mentioned the cases of extended master theorem which is difficult to find on the Internet. Either u add that answer or please put the link for those three cases of extended master theorem. $\endgroup$ – Kishan Kumar Jan 5 '18 at 13:13
  • $\begingroup$ @KishanKumar I added them to the reference question: cs.stackexchange.com/a/86285/683. $\endgroup$ – Yuval Filmus Jan 5 '18 at 14:00
0
$\begingroup$

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$

Improve this answer
$\endgroup$
2
  • $\begingroup$ Doesn’t look right to me. T(2^20) = 2^40/400+4*2^36/324+16*2^32/256 etc =O(n^2/ log n ^2) $\endgroup$ – gnasher729 Jan 3 '18 at 8:28
  • $\begingroup$ I don't get the substitution. Please elaborate. $\endgroup$ – Kishan Kumar Jan 3 '18 at 12:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.