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.