Asymptotic Complexity

Complexity Analysis: formally determine the efficiency of algorithms.

Can't we just code up the algorithm, run the program on test data, and measure execution time and memory requirements?

1. CPU time is affected by many factors not all related to the algorithm:
   • which computer, how heavily is it loaded
   • which programming language, which compiler
   • hidden factors can swamp the ones you're trying to measure:
     • array-bounds checking
     • relative speeds: array indexing, record access and pointer following,
     • overhead for procedure calls
     • I/O

2. Which test data? Efficiency must typically be expressed as a function of the input.