0

$T(n) = T(n -1 ) + n^c $ for c >= 1 , T(1) = 1
I tried to solve it using the iterative method but then I didn't know how to finish if for k

$T(n-1) = T(n-2) +(n-1)^c$

$T(n) = T(n-2) +(n-1)^c + n^c$

$T(n-2) = T(n-3) +(n-2)^c$

$T(n) = T(n-3) +(n-2)^c +(n-1)^c + n^c$

$T(n-3) = T(n-4) + (n-3)^c $

$T(n) = T(n-4) + (n-3)^c +(n-2)^c +(n-1)^c + n^c$

Then for k $T(k) = T(n-k) + .....(n-3)^c + (n-2)^c + (n-1)^c + n^c $ So k = n -1
Then $T(k) = 1 + .....(n-3)^c + (n-2)^c + (n-1)^c + n^c$

but how can I convert the rest to summation?

S_04
  • 9
  • Use the integral $\int_{x=0}^n x^c dx = \frac{n^{c+1}}{c+1}$. Try to show that $T(n) - O(n^c) \le \frac{n^{c+1}}{c+1} \le T(n) + O(n^c)$ – EnEm Sep 30 '22 at 13:01

1 Answers1

1

The left side of your last two identities should be $\ T(n)\ $ rather than $\ T(k)\ $. By putting $\ k=n-1\ $ in the second last identity, you will actually get \begin{align} T(n)&=T(1)+\dots+(n-3)^c+(n-2)^c+(n-1)^c+n^c\\ &=1+\dots+(n-3)^c+(n-2)^c+(n-1)^c+n^c\\ &=\sum_{j=1}^nj^c \end{align} for your last identity.

lonza leggiera
  • 28,646
  • 2
  • 12
  • 33