We provide an $O(n^2 \log {1 \over \delta})$ time randomized algorithm to check whether a given operation $\circ :S \times S \rightarrow S$ is associative (where $n=|S|$ and $\delta>0$ is the error probability required of the algorithm.) We prove that (for any constant $\delta$) this performance is optimal up to a constant factor even in case the operation is ``cancellative''. No sub-$n^3$ time algorithm was previously known for this task.

More generally we give an $O(n^c)$ time randomized algorithm to check whether a collection of $c$-ary operations satisfy any given ``read-once'' identity.