Algorithms in a Nutshell

Reporting

It is instructive to review the actual results when computed on the same platform, in this case a Linux 2.6.9-67.0.1.ELsmp i686 (this machine is different from the desktop PC and high-end computer mentioned earlier in this chapter). We present three tables (Tables A-3, A-5, and A-6), one each for Java, C, and Scheme. In each table, we present the millisecond results and a brief histogram table for the Java results.

Table A-3. Timing results of 30 computations in Java

n	average	min	max	stdev	#
1,000,000	8.5	8	18	0.5092	28
2,000,000	16.9643	16	17	0.1890	28
3,000,000	25.3929	25	26	0.4973	28
4,000,000	33.7857	33	35	0.4179	28
5,000,000	42.2857	42	44	0.4600	28

The aggregate behavior of Table A-3 is detailed in histogram form in Table A-4. We omit from the table rows that have only zero values; all nonzero values are shaded in the table.

Table A-4. Individual breakdowns of timing results

time (ms)	1,000,000	2,000,000	3,000,000	4,000,000	5,000,000
8	15	0	0	0	0
9	14	0	0	0	0
16	0	2	0	0	0
17	0	28	0	0	0
18	1	0	0	0	0
25	0	0	18	0	0
26	0	0	12	0	0
33	0	0	0	7	0
34	0	0	0	22	0
35	0	0	0	1	0
42	0	0	0	0	21
43	0	0	0	0	8
44	0	0	0	0	1

To interpret these results for Java, we turn to statistics. If we assume that the timing of each trial is independent, then we refer to the confidence intervals described earlier. If we are asked to predict the performance of a proposed run for n=4,000,000, ...