2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "The solution shows a solution using master method to prove the answer as O(n)" -- please re-check both the problem statement and the solution, because this seems wrong. Case 1 and 2 certainly don't apply since here, $f \in \omega(n \log^k n)$ for all $k$. I didn't check if case 3 applies, but if it does the answer is not $O(n)$. $\endgroup$ – Raphael Jan 4 '18 at 15:35
  • $\begingroup$ cs.stackexchange.com/questions/86194/… Please see the accepted answer for this question. $\endgroup$ – someone1 Jan 4 '18 at 15:37
  • $\begingroup$ I don't why it's been accepted, it clearly doesn't apply to the question. $\endgroup$ – Raphael Jan 4 '18 at 16:19
  • $\begingroup$ Doesn't the accepted version's case for c = -1 work? $\endgroup$ – someone1 Jan 4 '18 at 17:05
  • $\begingroup$ No, you have $n^2$ in $f$ but $\log_b a = 1$. $\endgroup$ – Raphael Jan 4 '18 at 17:38
0
$\begingroup$

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*} $$

$\endgroup$
  • $\begingroup$ Sure, I see that. However, could you possibly help me out in understanding the different answers(if they are even different) using the 2 substitutions I've made, and how they compare with your asymptotic statements. $\endgroup$ – someone1 Jan 5 '18 at 19:29
  • $\begingroup$ Since we're all solving the same equation using the same method (repeated substitution), we are all getting the same answer. The only question is how to estimate the sums involved. What you call a substitution is just one step in estimating the sum. If you pursue your methods enough, you will have reached the same asymptotic series as in my answer – after all, when estimating the same expression, you must be getting the same estimates. $\endgroup$ – Yuval Filmus Jan 5 '18 at 20:09

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.