Computer Algorithms II Lecture Notes

4 October 2007 • Performance Estimation in Practice

• Debian testing running on a 1.6 GHz laptop, 775 Mbyte main store, g++ ver. 4.2.1 with -O3 optimization.

• Data points are the average of 10 runs.

amortization		input size		runtime
elements		elements		μsec.		std. dev.
1		10000		57342		2177
		20000		211607		29208
		30000		551161		144431
		40000		1071085		566159
		50000		3138594		767406
		60000		6371371		1139596
		70000		10214778		1695895
		80000		15953099		2295461
		90000		23742746		2895472
		100000		32754648		3057679
100		10000		929		86
		20000		3244		216
		30000		5266		1534
		40000		22618		3978
		50000		49666		3967
		60000		39645		22739
		70000		63876		34533
		80000		186420		18778
		90000		173432		55166
		100000		244996		63781
200		10000		602		47
		20000		1936		181
		30000		3430		907
		40000		11887		1851
		50000		18577		4017
		60000		32234		6320
		70000		64913		4964
		80000		93491		6740
		90000		95899		24794
		100000		124151		27933