Correctness
Tags: #◇CCDSALG #◇Algorithms #◇Computer Science #◇Computational Complexity #◇Efficiency #◇Algorithm Design Paradigms #◇Analysis of Algorithms #◇Mathematical Foundations of Computing #◇Data Structures #◇Time Complexity #◇Space Complexity
◇Overview
Correctness is the property that an algorithm produces the correct output for every valid input and terminates in finite time.
◇Key Concepts
Partial correctness vs. total correctness Loop invariants for proving correctness Mathematical induction as a proof tool Correctness is one of the key ◇Algorithm design issues
◇Details / Theory
Definition
An algorithm is correct if, for every valid input, it:
- Terminates (halts in finite time), and
- Produces the correct output as specified.
Partial vs. Total Correctness
Partial correctness: If the algorithm terminates, the output is correct. Total correctness: The algorithm always terminates and the output is correct.
Total correctness = Partial correctness + Termination.
Loop Invariants
A loop invariant is a property that holds true before and after each iteration of a loop. It is used to prove correctness of iterative algorithms.
Three steps of a loop invariant proof:
- Initialization: The invariant is true before the first iteration.
- Maintenance: If the invariant is true before an iteration, it remains true after the iteration.
- Termination: When the loop terminates, the invariant (combined with the exit condition) gives us the desired result.
Example: Correctness of Linear Search
Loop invariant: At the start of iteration , the target is not in arr[0..i-1].
Initialization: Before , no elements have been checked — trivially true. Maintenance: If arr[i] != target, then target is not in arr[0..i]. Termination: Either arr[i] == target (found) or (not in array).
Proving Correctness of Recursive Algorithms
For recursive algorithms, correctness is often proved using mathematical induction:
Base case: Show the algorithm is correct for the smallest input. Inductive step: Assume correctness for inputs smaller than , prove for input .
◇Common Pitfalls
Confusing partial and total correctness — an algorithm can be partially correct but never terminate. Choosing a loop invariant that is too weak to prove the desired result. Forgetting the termination argument in a total correctness proof.
◇Summary
TL;DR — Correctness means an algorithm terminates and produces the right output for all valid inputs. It is proved using loop invariants (iterative) or mathematical induction (recursive).
◇Links
Related: ◇Algorithm — ◇Efficiency — ◇Algorithm Analysis — ◇Loops — ◇Recursion Source / Reference: Handout 01, Page 2
◇References & Navigation
- Previous Topic: ◇Core Concepts
- Next Topic: ◇Declarations
- Related Notes: ◇Algorithm Analysis, ◇Core Concepts
ACTIVE RECALL VERIFICATION
Select an answer to verify conceptual comprehension and reveal the technical rationale.
What are the two requirements for an algorithm to be considered "correct"?
What distinguishes total correctness from partial correctness?
What does the "Initialization" step of a loop invariant proof verify?
Which of the following describes the "Maintenance" step in proving correctness using loop invariants?
What is the final step in a loop invariant proof that gives the desired result?
In the linear search example, what is the loop invariant at the start of iteration ?
What is the standard mathematical tool used to prove the correctness of recursive algorithms?
What is a common pitfall when proving correctness?
What does the inductive step in a mathematical induction proof typically involve?
Which of the following is true about partial correctness?