search
Log In
0 votes
137 views

How to solve the following recurrence relation?

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

T(n) = 1 , n<= 7

in Algorithms 137 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 ??

2
$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.

Related questions

1 vote
1 answer
1
209 views
how to compute time complexity of this kind of recurrence relation- T(n)=T(n/2)+T(n/4)+T(n/8)+n
asked Oct 27, 2018 in Algorithms aditi19 209 views
0 votes
0 answers
2
234 views
I got this question from here https://gateoverflow.in/169286/time-complexity Is this Question Correct i have doubt . If correct please explain Which of the following statements is/are TRUE? $i)$ The time complexity of recurrence relation $A(n) = 3A(n/2)+n^{2} $is asymptotically ... $O( 7 ^ {n/53})$ is asymptotically faster But i am not able to get the answer because of question statement .
asked Aug 22, 2018 in Algorithms Rishav Kumar Singh 234 views
7 votes
1 answer
3
419 views
Consider the following piece of pseudo-code: A(n){ if(n==0) return 1; return A(√n) + B(n) + C(n) + D(n); } B(n){ if (n==0) return n; return B(n-1); } C(n){ return A (√n); } D(n){ return n; } What is the time complexity in terms of Big $\Theta$ notation for the function call to procedure A? $\Theta(n)$ $\Theta(n \log n)$ $\Theta(n \log \log n)$ $\Theta(n^2 \log n)$
asked Dec 27, 2018 in Algorithms Ruturaj Mohanty 419 views
0 votes
4 answers
4
2.4k views
I was wondering whether the recurrence T(n) = T(n/2) + 2n could be solved by using master theorem, and what would be the way. I tried solving the recurrence but can't. There is no mention to it in CLRS book. Please help. Thanks in advance.
asked Sep 28, 2018 in Algorithms mohitrai0_0 2.4k views
...