# Using Iterative method to find recurrence relation vs Master Theorm

I'm trying to solve this recurrence relation using the iterative method and i keep getting the different answer from using the master theorem.

\begin{aligned} T(n) &= 5T(n/2) +n^2 \\ &= 5^2 T(n/4) + (5/4)n^2 + n^2 \\ &= 5^3 T(n/8) + (5/4)^2 n^2 + (5/4)n^2 + n^2 \\ &= 5^k T(n/(2^k)) + n^2 \sum_{i=0}^{k-1}(5/4)^i \end{aligned}

$$n = 2^k => \ln(n) = k$$

\begin{aligned} &=5^{\ln(n)} T(1) + n^2 * \Theta(5^{\ln(n)}) \\ &= n^{\ln(5)} + n^2 * \Theta(n^{\ln(5)}) \end{aligned}

$$O(n^2 * n^{\ln(5)}) = O(n^{2+\ln(5)})$$

Right?

According to the master Theorem,

$$a= 5$$; $$b=2$$; $$p=0$$; $$k=2$$; $$5>4$$

This result in $$\Theta(n^{\ln(5)})$$ for this problem,

So, do I ignore the $$n^2$$ in the iterative method? Did I do it incorrectly? If it correct, then why is there a difference between master Theorem and iterative method? Master Theorem have a tighter constraint?

Check your maths. The sum with (5/4)^i is much smaller than theta(5^ln n).

Intuitively, T(n) = 5 T(n/2) gives you growth of n^(ln 5)= n^2 * n (ln 1.25). Adding another O (n^2) shouldn't make a difference.

You have been calculating correctly all along, except when it comes to $$\sum_{i=0}^{k-1}(\frac54)^i$$, where $$n=2^k$$.

Note that $$\sum_{i=0}^{k-1}(\frac54)^i = \frac{1-(\frac54)^k}{1-\frac54} = 4((\frac54)^k - 1) = 4\cdot2^{\ln(\frac54)k} - 4 = 4n^{\ln(\frac54)} - 4$$, where $$\ln(x)$$ means $$\log_2(x)$$.

So you would have

\begin{aligned} T(n) &= 5^k T(n/(2^k)) + 4n^2n^{\ln(\frac54)} - 4n^2 \\ &=n^{\ln(5)} T(1) + 4n^{\ln(5)} - 4n^2 \\ &=(T(1) + 4)n^{\ln(5)} - 4n^2 \\ &= O(n^{\ln(5)}) \end{aligned}

The result above obtained by iterative method is, as we should have been expecting, indeed consistent with the result obtained by the master Theorem.