1 votes 1 votes T(n) = T(n-1) + n^4 Algorithms algorithms time-complexity + – This_is_Nimishka asked Mar 29, 2022 This_is_Nimishka 565 views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply Shoto commented Mar 29, 2022 i edited by Shoto Mar 30, 2022 reply Follow Share $T(n) = T(n-1) + n^4$ $T(n) = T(n-2) + n^4 + (n-1)^4$ $T(n) = T(n-3) + n^4 + (n-1)^4 + (n-2)^4$ . . . $T(n) = T(n-k) + n^4 + (n-1)^4 + (n-2)^4 + … + (n-k+1)^4$ Taking base case T(1) = 1 since it is not mentioned, $n-k = 1 => k = n-1$ $T(n) = T(1) + n^4 + (n-1)^4 + … + (2)^4$ $T(n) = 1^4 + 2^4 + 3^4 + … + n^4$ $T(n) = \frac{n(n+1)(2n+1)(3n^2+3n+1)}{30} = O(n^5)$ 2 votes 2 votes This_is_Nimishka commented Mar 30, 2022 reply Follow Share Thanks. I am a newbie in algorithms and I was struggling here. Thank you so much. :-) 1 votes 1 votes Shoto commented Mar 30, 2022 reply Follow Share @This_is_Nimishka no problem :) 0 votes 0 votes Please log in or register to add a comment.