What is the running time of the PageGather algorithm?
We summarize here; a more complete analysis is found
in [15].
Let *L* be the number of page views in the log and
*N* the number of pages at the site.
In step (1), we must group the page views by their originating machine.
We do this by sorting page views by origin and time, which requires
*O*(*L log L*) time.
In step (2), we must process the log and create a matrix of size *O*(*N ^{2}*),
which requires