Overview
This lecture explains the difference between algorithm analysis (a priori analysis) and program testing (a posteriori testing), focusing on time and space considerations.
A Priori Analysis (Algorithm Analysis)
- Analysis is done on algorithms before implementation.
- Evaluates time and space requirements using mathematical functions.
- Results are independent of programming language, hardware, and operating system.
- Provides a theoretical time and space function, not actual measured values.
A Posteriori Testing (Program Testing)
- Testing is performed on actual programs after implementation.
- Involves running the program and measuring execution time and memory use.
- Results depend on hardware, operating system, and programming language.
- Reports real-world metrics such as seconds, milliseconds, or bytes used.
Comparison: Algorithms vs. Programs
- Algorithm analysis is theoretical and general; results apply to any implementation.
- Program testing is practical and specific; results vary by environment.
- Algorithms yield time/space functions, while programs yield actual measured values.
Key Terms & Definitions
- A Priori Analysis — Theoretical analysis of algorithms to estimate time and space before coding.
- A Posteriori Testing — Measurement of time and space by running implemented programs.
- Algorithm — A step-by-step procedure for solving a problem, independent of language or hardware.
- Program — An implementation of an algorithm in a specific language on a specific system.
Action Items / Next Steps
- Review examples of time and space functions for common algorithms.
- Prepare to compare a priori analysis results with a posteriori test data.