The Gateway to Computer Science Excellence
0 votes
96 views

How to solve the following recurrence relation?

T(n) = T(n-6) + n2 , n>7

T(n) = 1 , n<= 7

in Algorithms by (263 points) | 96 views
0
$O(n^3)$ ?
0

using substitution method

you will get o(n3)

0

@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 ??

+1
$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.

Please log in or register to answer this question.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,291 answers
198,209 comments
104,890 users