Algoritmo de Marzullo

Si el resultado deseado es un valor mejor de aquel intervalo entonces una aproximación sería tomar el centro del intervalo como el valor, que estuvo especificado en el original algoritmo de Marzullo.

El algoritmo descrito abajo es fácilmente parametrizable con el número máximo de estimaciones incorrectas.

La descripción del algoritmo utiliza las variables siguientes: best (número más grande de overlapping los intervalos encontrados), cnt (número actual de intervalos overlapping), beststart y bestend (el principio y fin del intervalo mejor encontrado tan lejano), i (un índice), y la tabla de tuplas.

Teniendo en cuenta el requisito de tiempo asintótico el algoritmo puede considerar construir la tabla, ordenándolo y buscándolo.

El orden puede ser hecho en O(n log n) tiempo, y esto domina el armado y la búsqueda se realiza por etapas que se van mejorando en tiempo lineal.

Por tanto, actualizar datos para una fuente y encontrar el mejor intervalo puede ser hecho en O(n) tiempo.