Editing Marzullo's algorithm (section)

==Efficiency==
Marzullo's algorithm is efficient in both space and time.  The [[asymptotic]] space usage is [[Big O notation|O(n)]], where n is the number of sources.  In considering the asymptotic time requirement the algorithm can be considered to consist of building the table, sorting it and searching it.  Sorting can be done in O(n log n) time, and this dominates the building and searching phases which can be performed in [[linear]] time.  Therefore, the time efficiency of Marzullo's algorithm is [[Big O notation|O(n log n)]].

Once the table has been built and sorted it is possible to update the interval for one source (when new information is received) in linear time.  Therefore, updating data for one source and finding the best interval can be done in O(n) time.