I am trying to find a function f(k) such that $S_k=\sum_{n=1}^{k^2-1}(\lfloor\sqrt{n}\rfloor)=\Theta(f(k))$. What I have done so far:
Ignoring the floor asymptotically we get:
$$S_k=\sum_{n=1}^{k^2-1}(\sqrt{n})=\Theta(f(k))$$
$g(n)=\sqrt{n}$ is a monotonically increasing function so we can approximate the sum by integrals:
$$\int_0^{k^2-1}\sqrt{x}dx\leq\sum_{n=1}^{k^2-1}(\sqrt{n})\leq\int_1^{k^2}\sqrt{x}dx$$
Let $A=\int_0^{k^2-1}\sqrt{x}dx$ and $B=\int_1^{k^2}\sqrt{x}dx$
Starting from the second integral:
$B=\int_1^{k^2}x^{1/2}dx=[\frac23x^{3/2}]_1^{k^2}=\frac23k^3-\frac23=O(k^3)$ (Big-Oh notation) beacause for each $n\geq n_0=1, c=\frac23$ the following is true: $0 < B\leq ck^3=\frac23k^3$
So that's an upper bound for $S_k$ that is $S_k=O(k^3)$. As far as I know $S_k=\Omega(k^3)$ and this way $S_k=\Theta(k^3)$. But I cannot prove the lower bound. For A the following is true:
$A=\int_0^{k^2-1}x^{1/2}dx=[\frac23x^{3/2}]_0^{k^2-1}=\frac23(k^2-1)^{3/2}$
How can I proceed further?
Best Answer
For every $1\leqslant i\leqslant k$ and every $i^2\leqslant n\leqslant(i+1)^2-1$, one has $\lfloor\sqrt{n}\rfloor=i$ hence $$S_k=\sum_{i=1}^k\sum_{k=i^2}^{(i+1)^2-1}i=\sum_{i=1}^ki\,(2i+1)=\frac16k(k+1)(4k+5),$$ hence $$S_k=\Theta(k^3).$$