0 votes 0 votes How to solve the following recurrence relation? T(n) = T(n-6) + n2 , n>7 T(n) = 1 , n<= 7 Algorithms time-complexity asymptotic-notation recurrence-relation algorithms + – garvit_vijai asked Nov 17, 2018 garvit_vijai 449 views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply goxul commented Nov 17, 2018 reply Follow Share $O(n^3)$ ? 0 votes 0 votes adarsh_1997 commented Nov 17, 2018 reply Follow Share using substitution method you will get o(n3) 0 votes 0 votes Gurdeep Saini commented Nov 21, 2018 reply Follow Share @adarsh @goxul i got T(n)=1+132+192+252+............+n2 if it is right how to solve it further or if it is wrong then what is right ?? 0 votes 0 votes goxul commented Nov 21, 2018 reply Follow Share $T(n) = T(n-6k) + \Sigma_{0}^{k-1} (n - i)^2$, $n -6k = 7$. Just expand the summation and you should get a $n^3$ term there. 2 votes 2 votes Please log in or register to add a comment.