Question

How to solve this recurrence T(n)=17T(7n)+n^4

Comments

can u  give detail solution?

---

@ankitgupta.1729 sorry sorry i got my mistake what blunder i have made 

---

@Chandrabhan Vishwa 1 sorry for the late reply. As I have mentioned, you can directly use substitution here to solve the given recurrence.

$T(n) = 17T(7n) + n^4$
$T(n) = 17[17*T(7^2n) + (7n)^4] + n^4 = 17^2 T(7^2n) + [17*(7n)^4 + n^4 ]$
$T(n) = 17^3 T(7^3n) + [17^2(7^2n)^4 + 17(7n)^4 + n^4]$
$....$
$T(n) = 17^k T(7^k n) + [17^{k-1} (7^{k-1}n)^4 +...+ 17^2(7^2n)^4 + 17(7n)^4 + n^4 ]$

Let $T(1) = 1 \Rightarrow 7^kn = 1 \Rightarrow 7^k = \frac{1}{n} \Rightarrow k = \log_7 (\frac{1}{n})$
So,
$T(n) = 17^{k} + n^4 [(17*7^4)^{k-1} +...+(17*7^4)^2 + (17*7^4)^1 + 1]$
$T(n) = 17^k + n^4 \left(\frac{(17*7^4)^k - 1}{17*7^4 - 1} \right)$

Now, put $k = \log_7(\frac{1}{n})$ in the above equation which will be your solution for the given recurrence.

Answer 1

We can solve it using master theoram. The answer is theta(n^4)

Comments

How can you solve this using master’s theorem? Can you please answer in detail.