This MathOverflow question seems to indicate that the state of the art in computing $$ M(x)=\sum_{n\le x}\mu(n) $$ takes time $\Theta(n^{2/3}(\log\log n)^{1/3}),$ which matches my understanding. Recently I came across a paper [1] which gives, almost as an afterthought, an algorithm for computing $M(x)$ in $O(\sqrt x)$ time (in section 3.2).

The algorithm itself seems to be correct, being derived in a straightforward way from the identity $$ M(x)=1-\sum_{d\ge2}M(x/d). $$ But the claim that is runs in time $O(\sqrt x),$ or even $O(x^{1/2+\varepsilon}),$ seems unusual enough for me to ask for verification.

First, this would be a major breakthrough in computing $M(x),$ enough that I would think it would merit more mention than a substep of another algorithm. At the least, I would expect a mention that previous algorithms were slower.

Second, the algorithm is very simple, so that if the time is as indicated the implied constant should be low and the algorithm should be practical. In any case it is not hard to program.

Third, on coding the algorithm I found it to be very slow. In fact, it was slower for those values tested than `sum(n=1, 10^7, moebius(n))`

in GP which involves factoring each number up to $10^7.$ The time needed to factor numbers of those sizes is about $\sqrt x/\log x$ on average, so that's a $\Theta(n^{3/2}/\log n)$ algorithm (admittedly, well-optimized) beating a $\Theta(n^{1/2})$ algorithm. The constants would have to be worse by a factor of $5\cdot10^6$ for that to happen, and there's nothing in the algorithm to suggest anything that bad.

Of course I may have miscoded it (though I obtained the correct answer) or there may be reasons why the constant factors would be so high for this algorithm. But in any case this seemed suspicious enough to bring up here that I might be enlightened in any case.

Of course even if the result claimed is not correct this is no mark against the author, as the paper is only a preprint and the claim is peripheral in any case.

[1]: Jakub Pawlewicz, Counting square-free numbers (2011), arXiv:1107.4890.