Approximating a series for asymptotic upper bound

Question

So I stumbled upon a question here to find an asymptotic bound for the recurrence $$ T(n) = 4T(n/4) + \left( \frac {n} {\log n} \right)^2 $$

The solution shows a solution using master method to prove the answer as $O(n)$ However, I tried to solve it using substitution as:

$$T(\frac {n} {4^i}) = 4^{i+1} T(\frac {n} {4^{i+1}} ) + \sum_{j=0}^{i} \frac {n^2} {4^j {(\log \frac{n}{4^j})^2} }$$

I then get $$ T(n) = 4^{x+1}(Base Constant) + \sum_{j=0}^{logn -1} \frac {n^2} {4^j {(log \frac{n}{4^j})^2} }$$ $x=\log n$

Now for the summation: $$n^2\sum_{j=0}^{\log n -1} \frac {1} {4^j {(log(n) - j\log (4))^2} }$$

All logarithms to be taken base 4: $n^2\sum_{j=0}^{\log n -1} \frac {1} {4^j {(\log (n) - j)^2} }$

Now, the first substitution I made was $t = \log n -j $

$n^2\sum_{j=1}^{\log n -1} \frac {4^t} {4^{\log n} {t^2} }$

= $n^2\sum_{j=1}^{\log n -1} \frac {4^t} {n {t^2} }$ = $n\sum_{j=1}^{\log n -1} \frac {4^t} { {t^2} }$

Using wolfram and wkipedia, the sum comes out to $Li2(4) -n Lerch Function(4,2,\log (n)-1)$

I could simple assume this is constant and that would prove my bound to be $O(n)$ as the master theore suggests, but I ahve no proof to bound the Lerch and dilogarithmic function.

Another substitution I tried was

$$ t=4^j (\log n -j)^2 $$ which gives me $$n^2 H(n) - H((\log n)^2) $$ where $H(n)$ is the nth harmonic number I again could not reach a bound for this, besides $\log (n) - \log (\log n) $ which is quite different from my first substitution.

If someone could help me with what error I'm making, or why the substitutions yield different results that would be great.

Answer 1

To make things a bit simpler, let us assume that we use base 4 logarithm. Following your steps, for $n = 4^k$ and $T(1) = 0$ we get $$ \begin{align*} T(n) &= \frac{n^2}{(\log_4 n)^2} + 4\frac{(n/4)^2}{(\log_4 n-1)^2} + 16\frac{(n/16)^2}{(\log_4 n - 2)^2} + \cdots \\ &= \frac{n^2}{(\log_4 n)^2} \left[ 1 + \frac{1}{4(1-1/\log_4 n)^2} + \frac{1}{16(1-2/\log_4 n)^2} + \cdots \right]. \end{align*} $$ Let us now use the series expansion $$ \frac{1}{(1-x)^2} = 1 + 2x + 3x^2 + 4x^3 + \cdots. $$ Substituting this in the expression above, we get $$ \begin{align*} \frac{T(n)}{n^2/\log^2_4n} &= 1 + \frac{1}{4} + \frac{1}{16} + \cdots \\ &+ 2\left[ \frac{1}{4\log_4 n} + \frac{2}{16\log_4 n} + \cdots \right] \\ &+ 3 \left[ \frac{1}{4\log_4^2n} + \frac{2^2}{16\log_4^2n} + \cdots \right] + \cdots \\ &\approx \frac{4}{3} + \frac{8/9}{\log_4 n} + \frac{20/9}{\log_4^2 n} + \cdots \end{align*} $$ The error in the approximation is polynomially small: for example $$ \sum_{k=0}^{\log_4 n-1} \frac{1}{4^k} = \frac{4}{3} - \frac{4/3}{4^{\log_4 n}} = \frac{4}{3} - \frac{4/3}{n}. $$ The error is somewhat larger for the other summands, but still polynomially small. Taylor's theorem (or direct calculation) shows that if we truncate the series for $1/(1-x)^2$ after the term $(d+1)x^d$ then we get an error of $O(x^{d+1})$. Altogether, this shows that the following asymptotic statements hold: $$ \begin{align*} T(n) &= \frac{4}{3} \frac{n^2}{\log_4^2 n} + O\left(\frac{n^2}{\log_4^3 n}\right), \\ T(n) &= \frac{4}{3} \frac{n^2}{\log_4^2 n} + \frac{8}{9} \frac{n^2}{\log_4^3 n} + O\left(\frac{n^2}{\log_4^4 n}\right), \\ T(n) &= \frac{4}{3} \frac{n^2}{\log_4^2 n} + \frac{8}{9} \frac{n^2}{\log_4^3 n} + \frac{20}{9} \frac{n^2}{\log_4^4 n} + O\left(\frac{n^2}{\log_4^5 n}\right), \ldots \\ \end{align*} $$