  The fast marching algorithm computes an approximate solution to the eikonal
equation in O(N log N) time, where the factor log N is due to the
administration of a priority queue. Recently, Yatziv, Bartesaghi and Sapiro
have suggested to use an untidy priority queue, reducing the overall complexity
to O(N) at the price of a small error in the computed solution. In this paper,
we give an explicit estimate of the error introduced, which is based on a
discrete comparison principle. This estimates implies in particular that the
choice of an accuracy level that is independent of the speed function F results
in the complexity bound O(Fmax /Fmin N). A numerical experiment illustrates
this robustness problem for large ratios Fmax /Fmin .
