Data Structures & Algorithms Notes Page
Correctness and Analysis of Algorithms
Deduction:
- Prove correctness by logically reasoning through the steps of the algorithm.
Induction:
- Use mathematical induction to prove correctness step-by-step (e.g., prove the algorithm works for a base case, then assume it works for one step and prove it works for the next).
Contradiction:
- Assume the opposite of what you want to prove, and show it leads to a contradiction.
Limitations on Measuring Run Time
Hardware Dependencies:
- The speed of an algorithm depends on the machine's speed and resources (e.g., processor speed)
Problem Size:
- Larger inputs may cause the algorithm to run much slower.
External Factors:
- Disk access, network speed, and other I/O operations can affect runtime.