Computing the Mertens function

This article presents an algorithm to compute Mertens function in $O(x^{2/3}(\log \log x)^{1/3})$ time and $O(x^{1/3}(\log \log x)^{2/3})$ space, I wonder if it is the same one you are referring to. On the other hand people sometimes make use of certain recursions such as the results in this paper to compute things about the Mertens function. This paper seems to claim that these algorithms haven't been improved upon.

As I indicate in the answer Mertens' function in time $O(\sqrt x)$, there is a method in Lagarias-Odlyzkos 1987 paper "Computing $\pi(x)$ an analytic method" (which I sketch in that answer) that calculates $M(x)$ on $O(x^{1/2+\epsilon})$ time. The Kotnik-Van de Lune paper that Gjergji Zaimi cites indeed also cites this paper. While the methods that depend on values of the Riemann zeta-function (like the Lagarias-Odlyzko method) might be asymtotically faster, the combinatorial identities are simpler to implement, and might also be faster depending on the ranges of $x$ considered.

Perhaps the simplest sub-linear method is to rewrite the identity $$\sum_{k=1}^n M \left( \left\lfloor \frac n k \right\rfloor \right) = 1$$

in the form

$$M(n) = 1 - \sum_{k=2}^n M \left( \left\lfloor \frac n k \right\rfloor \right)$$

The observation is that $\lfloor n/k\rfloor$ is constant for many values of large $k$, in particular $k > \sqrt n$, so we can use the technique I describe in my math.SE post about computing the totient summatory function in sub-linear time: $$M(n) = 1 - \sum_{k=2}^{\sqrt n} M \left( \left\lfloor \frac n k \right\rfloor \right) - \sum_{k=1}^{\sqrt n} \left( \left\lfloor \frac n k \right\rfloor - \left\lfloor \frac n {k+1} \right\rfloor \right) M(k)$$

adjusting the summation bounds if $\lfloor \sqrt{n} \rfloor = \left \lfloor \frac{n}{\lfloor \sqrt{n} \rfloor} \right\rfloor$.

This formula has time complexity $O(n^{3/4})$, and with some pre-computing tables as described in Deléglise, Marc; Rivat, Joöl. Computing the summation of the Möbius function. Experiment. Math. 5 (1996), no. 4, 291--295. we get an almost $O(n^{2/3})$ algorithm.