# Asymptotic dominance for sum of roots.

I'm trying to solve one of the tasks in the Algorithm Design Manual book from Steven Skiena. The goal is to place the functions into increasing asymptotic order.

$f_1(n)=\sum_{i=1}^n\sqrt{i}$,

$f_2(n)=\sqrt{n} \log{n}$,

$f_3(n)=n \sqrt{\log{n}}$,

$f_4(n)=12n^{\frac32}+4n$

With $f_2(n)$, $f_3(n)$, $f_4(n)$ it's pretty simple. But I don't understand how to resolve this function $f_1(n)=\sum_{i=1}^n\sqrt{i}$.

-
Hint: $$\int_0^n\sqrt{x}dx\le\sum_{i=1}^n\sqrt{i}\le\int_0^n\sqrt{x+1}dx$$
Edit: We know that $x \le \lceil x\rceil\le x+1$, so $$\int_0^n\sqrt{x}dx\le\int_0^n\sqrt{\lceil x\rceil}dx\le\int_0^n\sqrt{x+1}dx$$ but for $x\in (n-1,n]$ we have $\sqrt{\lceil x\rceil}=\sqrt{n}$, so we can write $$\int_0^n\sqrt{\lceil x\rceil}dx=\sum_{i=1}^n \int_{i-1}^i\sqrt{i}dx=\sum_{i=1}^n\sqrt{i}$$