I think, $C\sqrt{n}$ is an upper bound aswell. Take vector $x=(x_1,\dots,x_n)$ with $x_j=j^{-1/2}$. Then

$$ [Ax]_i=\sum\limits_{j\le n/i} j^{-1/2}, $$

what behaves like $C\sqrt{n/i}=C\sqrt{n}x_i$. But we know that if $[Ax]_i\leq C x_i$ for vector $x$ with positive coordinates, then larest eigenvalue of $A$ does not exceed $C$ (kind of Perron-Frobenius).

I think, $C\sqrt{n}$ is an upper bound aswell. Take vector $x=(x_1,\dots,x_n)$ with $x_j=j^{-1/2}$. Then $(Ax)_i$ behaves like $C\sqrt{n/i}=C\sqrt{n}x_i$. But we know that if $(Ax)_i\leq C x_i$ for vector $x$ with positive coordinates, then the largest eigenvalue of $A$ does not exceed $C$ (kind of Perron-Frobenius).

(This answer is very ugly displayed, I do not know why).