This is a comment on gowers' answer, but it is long enough that I am making it an answer on its own.
I don't think this quite works. If $[a_0, a_1, \ldots, a_i]=p_i/q_i$, and $x$ is the value of the infinite continued fraction, then $$|x-p_i/q_i|= 1/(q_i q_{i+1})-1/(q_{i+1} q_{i+2}) + \cdots \approx 1/(q_i q_{i+1}).$$ We have $a_{i+1} q_i < q_{i+1} < (a_{i+1} +1 ) q_i$, so $q_{i+1} \approx a_{i+1} q_i$.
If $a_i$ is a permutation of the integers which doesn't reorder them too much then $a_i$ is about $i$ so $q_i \approx i!$. Inverting Stirling's approximation, $i \approx \log q_i/\log \log q_i$.
So we have $$|x-p/q| \approx \frac{\log \log q}{q^2 \log q}.$$
This is consistent with Roth's theorem.
My hazy memory is that there is a conjecture that, for $\phi(q)$ a decreasing positive function, there is an algebraic number $x$ with infinitely many solutions to $|x-p/q| < \phi(q)$ if and only if $\sum q \phi(q)$ diverges. That would predict that the error rate above is consistent with being algebraic. Does any one know if I remember this correctly?
