Performance in Computing Deviations

To measure the performance in computing deviations, we carried out an experiment to run our program for various data sizes. The program was run on a PC which has a 600 MHz Pentium III processor and 192 MB of main memory with an Ultra2 Wide SCSI hard disk attached to it.

Table 1 shows the execution time in seconds to compute all the deviations for packet streams in traffic data of $N$ packets from a packet stream of $n$ packets for varying $n$ and $N$. In the top row of the table, the letter `K' means thousand or $10^3$, and the letter `M' means million or $10^6$. The result confirms that the computation time is $O(nN)$.

Table 1: Execution time (in seconds) to compute deviations

$n\backslash N$	1K	5K	10K	50K	100K	500K	1M
100	0.03	0.16	0.35	1.69	3.48	17.98	36.52
200	0.06	0.27	0.59	2.84	5.88	30.35	61.96
400	0.10	0.51	1.05	5.13	10.62	54.95	112.07
700	0.16	0.83	1.73	8.38	17.31	89.66	182.57