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

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.

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

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

• @KishanKumar I added them to the reference question: cs.stackexchange.com/a/86285/683. Jan 5, 2018 at 14:00

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$

• 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) Jan 3, 2018 at 8:28
• I don't get the substitution. Please elaborate. Jan 3, 2018 at 12:50
{"ft_lang_label":"__label__en","ft_lang_prob":0.9520949,"math_prob":0.99999154,"size":466,"snap":"2023-40-2023-50","text_gpt3_token_len":134,"char_repetition_ratio":0.10606061,"word_repetition_ratio":0.0,"special_character_ratio":0.28540772,"punctuation_ratio":0.05940594,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":1.0000085,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-12-06T09:00:39Z\",\"WARC-Record-ID\":\"<urn:uuid:ac2fc5ac-5f8c-4d89-bcc5-df7f2009a6d0>\",\"Content-Length\":\"189977\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:47c3d9d7-f9a4-4e23-82e2-75993021285c>\",\"WARC-Concurrent-To\":\"<urn:uuid:0e588510-fb78-4e6b-8026-3d583cc720e2>\",\"WARC-IP-Address\":\"104.18.43.226\",\"WARC-Target-URI\":\"https://cs.stackexchange.com/questions/86194/solving-tn-4tn-4-n-log-n2\",\"WARC-Payload-Digest\":\"sha1:3DUHVJ4ZSX4E5TEG7EJFTSQIWVCH6L5J\",\"WARC-Block-Digest\":\"sha1:HWOO7NSSRAJEI2E7BW26BRXCYK6AALO6\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-50/CC-MAIN-2023-50_segments_1700679100583.31_warc_CC-MAIN-20231206063543-20231206093543-00312.warc.gz\"}"}