0
$\begingroup$

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.

$\endgroup$

2 Answers 2

2
$\begingroup$

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.

You can also easily get a tight upper bound by a direct application of the master theorem.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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