# Finding asymptotically tight upper bound of a recursion relation

Find an asymptotic tight upper bound for the following recursion relation: $$T(n)=5T(\frac{n}{5})+\log^2(n)$$

I tried to solve it by applying iteration: $$T(n)=5T(\frac{n}{5})+\log^2(n)=5(5T(\frac{n}{5^2})+\log^2(\frac{n}{5}))=\ldots=5^kT(\frac{n}{5^k})+\sum_{i=0}^{k-1}5^i\log^2(\frac{n}{5^i})$$ Now letting $$5^k=n$$, we have that $$k=\log_5(n)$$. Hence the last equality becomes: $$n\cdot T(1)+\sum_{i=1}^{\log_5(n)-1}5^i\log^2(\frac{n}{5^i})\stackrel{*}{\leq} n\cdot T(1)+\log^2(n)\sum_{i=0}^{\log_5(n)-1}5^i=n+\log^2(n)\cdot\frac{5^{\log_5(n))}-1}{4} =n+\frac{\log^2(n)(n-1)}{4}$$

Hence $$T(n)=O(n\log^2(n))$$. However, I'm not sure this is the correct answer. Is the bound I took in the step marked by $$*$$ not tight enough? Any help would be appreciated.

Your upper bound is not tight. Let $$n=5^k$$, as in you question. You can upper bound your summation by $$\sum_{i=1}^{k} 5^i \cdot \log^2 5^{k-i} \le 6 \sum_{i=1}^{k} 5^i (k-i)^2 = 6 \cdot 5^{k} \sum_{i=0}^{k-1} \frac{i^2}{5^i} = 5^k \cdot O(1),$$ where the last equality follows from the fact that the series converges to some positive constant. Indeed, by the ratio test: $$\lim_{i \to \infty} \frac{(i+1)^2}{5^{i+1}} \cdot \frac{5^i}{i^2} = \lim_{i \to \infty} \frac{i^2+2i+1}{5 i^2} = \frac{1}{5}.$$
This shows that $$T(n) = O(n)$$, which is tight. To prove that formally you also need to show a lower bound of $$\Omega(n)$$, which is easy using similar calculations.
Given, $$T(n)=5T(\frac{n}{5})+\log^2(n)$$ compare with $$T(n)=aT(\frac{n}{b})+n^k\log^p(n)$$(By master theorem) where $$a\geq1,b>1,k\geq 0$$ and $$p \in \mathbb{R}.$$
Since $$a> b^k$$, $$T(n) =\Theta(n^{\log_{b}a})$$ which is $$\Theta(n).$$