What is the average-case complexity of trial division?
By the prime number theorem, about a $1/\log(n)$ fraction of numbers in the range $[n/2,n]$ are prime.  We know that the algorithm will take $\Theta(\sqrt{n})$ time for each of them (since for all $x \in [n/2,n]$, we have $x = \Theta(\sqrt{n})$).  Therefore,

$$\mathbb{E}[T(X_n)] = \Omega\left({\sqrt{n} \over \log n}\right).$$

This is enough to establish that trial division is inefficient.  Also, since we have the upper bound

$$\mathbb{E}[T(X_n)] = O(\sqrt{n}),$$

we get a pair of upper and lower bounds that are almost matching.

It turns out one can show that the correct running time is

$$\mathbb{E}[T(X_n)] = \Theta\left({\sqrt{n} \over \log n}\right).$$

I'll show the argument below.  It's a bit detailed, so brace yourself.



There's an error in your post.  You claim that

$$\mathbb{E}[T(X_n)] = {\sum_{i=2}^n \xi(i) \over n-1},$$

but that is not correct.  The running time on input $i$ is not $\xi(i)$; the running time is $\min(\xi(i),\sqrt{i})$, since trial division aborts early as soon as it has tried all divisors $\le \sqrt{i}$.  Therefore, your expression for the running time is not correct.

Yuval Filmus found that your expression was analyzed on Math.SE, and apparently

$${\sum_{i=2}^n \xi(i) \over n-1} \sim {n \over 2 \log n},$$

but unfortunately this doesn't really tell us much about the running time of your trial division, due to the error I mentioned.



If we correct the error, we find

$$\mathbb{E}[T(X_n)] = {\sum_{t&lt;n} \xi(t) \over n-1} + \Theta\left(\sqrt{n} \over \log n\right),$$

where $t$ ranges over all composites less than $n$.  Now we can upper-bound the first term as follows:

$$\begin{align*}
\sum_{t &lt; n} \xi(t)
&amp;\le \sum_{p &lt; \sqrt{n}} \left\lfloor {n \over p} \right\rfloor \times p\\
&amp;\le \sum_{p &lt; \sqrt{n}} n\\
&amp;= n \times \#\{p : p &lt; \sqrt{n}, p \text{ prime}\}\\
&amp;= n \times O\left({\sqrt{n} \over \log n}\right).
\end{align*}$$

where the sum is over all primes $p$ that are at most $\sqrt{n}$, and using the prime number theorem in the last step to note that there are $O(\sqrt{n}/\log(\sqrt{n})) = O(\sqrt{n}/\log(n))$ many such primes $p$.

It follows that

$$\mathbb{E}[T(X_n)] = O\left(\sqrt{n} \over \log n\right),$$

so the simple bound given at the start of the answer was tight.