0 votes 0 votes Algorithms algorithms recurrence-relation + – darkswow asked Oct 18, 2022 • retagged Oct 18, 2022 by makhdoom ghaya darkswow 531 views answer comment Share Follow See all 7 Comments See all 7 7 Comments reply Show 4 previous comments Chandrabhan Vishwa 1 commented Oct 28, 2022 reply Follow Share can u give detail solution? 0 votes 0 votes shikhar500 commented Oct 28, 2022 reply Follow Share @ankitgupta.1729 sorry sorry i got my mistake what blunder i have made 0 votes 0 votes ankitgupta.1729 commented Dec 24, 2022 reply Follow Share @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. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes We can solve it using master theoram. The answer is theta(n^4) nishantsharma answered Jan 11, 2023 nishantsharma comment Share Follow See 1 comment See all 1 1 comment reply Aryanzzzz commented Jan 12, 2023 reply Follow Share How can you solve this using master’s theorem? Can you please answer in detail. 0 votes 0 votes Please log in or register to add a comment.