Complexity of $T(n) = T(n-10) + \sqrt{n}$ I'm using the iteration method to find the complexity of the following recurrence (I can't use the master theorem because it doesn't match the MT form).
$$
T(n) = T(n-10) + \sqrt{n} \text{ and } T(1) = 1
$$
Assuming my solution is correct, I have
$$T(n) = T(n-10i) + \sum_{j=0}^{i-1} \sqrt{n-10j} $$
that means
$$T(1) = 1 \text{ when } i = \frac{n-1}{10}$$
hence
$$T(N) = T(1) + \sum_{j=0}^{\frac{n-1}{10}} \sqrt{n-10j}$$
At this point I'm stuck. I'm not sure if I can simplify the sum by removing constants. My final result is something like $\Theta(n * \sqrt{n})$, but I definitely don't trust my result.
 A: Given a positive integer $n$, the recurrence easily provides 
$$T(n) = T(n’) + \sum_{j=0}^{\frac{n-n’}{10}} \sqrt{n’+10j},$$
where $1\le n’\le 10$ and $n=n’\pmod {10}$. We claim that the sum $S(n)$ is $\Theta (n^{3/2})$. Indeed, 
$$\int_{n’}^n \sqrt{x}dx=\frac 23 x^{3/2}\Big|_{n’}^n=\Theta (n^{3/2})$$ and 
$$S(n)- 10\int_{n’}^n \sqrt{x}dx=\sqrt{n’}+\sum_{j=1}^{\frac{n-n’}{10}} \sqrt{n’+10j}-10\int^{n’+10j}_{n’+10(j-1)}\sqrt{x}dx=
O(1)+O(n),$$ 
because for each $j$ 
$$0\le \sqrt{n’+10j}-10\int^{n’+10j}_{n’+10(j-1)}\sqrt{x}=$$ $$10\int^{n’+10j}_{n’+10(j-1)}\left(\sqrt{n’+10j}-\sqrt{x}\right)dx=O(1),$$
because for  each $x\in [n’+10(j-1), n’+10j]$ by Lagrange’s Theorem there exists $y\in (x, n’+10j)$ such that 
$\sqrt{n’+10j}-\sqrt{x}=\frac 1{2y}(n’+10j-x)=O(1)$. (I expect in fact the approximation of the sum by the integral is even $O(\sqrt{n})$).
Finally $T(n)=\Theta (n^{3/2})$.
A: Your result is correct, and it's relatively straightforward to show.  First of all, note that your sum is within $O(\sqrt{n})$ of $\sum_{i=1}^{\lfloor n/10\rfloor}\sqrt{10i}$ (can you see why?) and therefore within $O(\sqrt{n})$ of $\sqrt{10}f(\lfloor n/10\rfloor)$, where $f(t)=\sum_{i=1}^t \sqrt{i}$.  Now, note that $f(t)\leq t\sqrt{t}$ (since there are $t$ terms each of which is $\leq \sqrt{t}$); on the other hand, $f(t)\geq \sum_{i=t/2}^t\sqrt{i}$ $\geq (t/2)\sqrt{t/2}$ (since there are $(t/2)$ terms each of which is $\geq \sqrt{t/2}$) $=2^{-3/2}t\sqrt{t}$.  But now we've bounded $f(t)$ between $C_1t\sqrt{t}$ and $C_2t\sqrt{t}$ for constants $C_1$ and $C_2$, so $f(t)\in\Theta(t\sqrt{t})$, and finally your sum is in $\Theta(n\sqrt{n})$.
