Time complexity

Question

Answer 1

$T(n) = T(n-2) + n^{^{2}}$

$T(n-2) = T(n-4) + (n-2 )^{^{2}}$

$T(n-4) = T(n-6) + (n-4 )^{^{2}}$

so this goes on till n goes to zero

$n-2x = 0$

$\rightarrow x= \frac{n}{2}$

so finally

$T(n) = 1+n^{^{2}} + (n-2)^{^{2}}+(n-4)^{^{2}}..........$  $\frac{n}{2} times$

Each contain a $n^{2}$ term and they are $\frac{n}{2}$ of those so it will be $O(n^{3})$

Comments

Good Explaination!

Answer 2

Yes solution is O(n³)   solve it by mathematical induction. in end you will get a series of sum of square of first n natural number which will result in O(n^3) 

 O(n³)