Applying AM-GM, we get $$x_n^2\le \sum_{i=1}^{n-1}x_i$$We want to estimate the growing rate of $x_n$ and we have a suspicion that it's linear, so let us set $x_n=an+\Delta(n)$, where $a$ is a constant that will be determined later. We have, $$a^2n^2 +2an\Delta(n)+\Delta(n)^2 \le \frac{a(n-1)n}{2}+\sum_{i=1}^{n-1}\Delta(i)$$$$ 2an\Delta(n) \le \left(\frac{a(n-1)n}{2}-a^2n^2\right) - \Delta(n)^2 +\sum_{i=1}^{n-1}\Delta(i)\qquad(1)$$The plan is to divide both sides by $n$ so let's determine $a$ such that the term in the brackets of the right side of $(1)$ be of degree $n$ (not $n^2$ as it is now). It easily can be calculates that $a=1/2$. Putting it, we get $$\Delta(n)\le -\frac{1}{4} -\frac{\Delta(n)^2}{n} +\frac{1}{n}\sum_{i=1}^{n-1}\Delta(i) $$If we want just to solve problem we could write $$\Delta(n)\le \frac{1}{n}\sum_{i=1}^{n-1}\Delta(i) $$which yields $$\Delta(n)\le \max\{\Delta(i): i<n \}\,,\,\forall n>N$$hence $\Delta(n)\le \max\{\Delta(i): i\le N\}$. If we want to go a bit further, let's write $$\Delta(n)\le -\frac{1}{4}+ \frac{1}{n}\sum_{i=1}^{n-1}\Delta(i) $$Now, it can be seen that $\Delta(n)$ becomes negative from some place on, so for sufficiently large $n$ it holds $x_n<n/2$.

A slightly better bound can be obtained, $x_n\le \frac{n}{2}-\frac{\ln n}{4}$. See the details here.

Hi @dgrozev, please why you can choose $M_{n}= \max\{\Delta(i) : i < n\}$ independant from $n$, even if we look at only the first $N$ values, we dont necessary have $M_{n} \leq M_{N}$ for $n > N$. Am-I wrong ?

It was not properly written in #2, but I did it correctly in the reference given. Take $M:= \max\{\Delta(i): i\le N\}$. Because of $$\Delta(n)\le \max\{\Delta(i): i<n \}\,,\,\forall n>N$$you inductively obtain that $\Delta(n)\le M, n=N+1,N+2,\dots$. That's it. ... But as it turns out, the growth rate of $x_n$ is not $n/2$. We have $$x_n=\frac{\pi}{8}n+o(n).$$See the same link.