# Time Complexity

137 views

How to solve the following recurrence relation?

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

T(n) = 1 , n<= 7

0
$O(n^3)$ ?
0

using substitution method

you will get o(n3)

0

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.

## Related questions

1 vote
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
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 .
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)$