✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-008

Algorithm Correctness

A study of algorithm correctness, explaining how an algorithm can be shown to satisfy its specification for every valid input through preconditions, postconditions, loop invariants, termination arguments, and formal reasoning.

Explanation

Overview

Algorithm correctness is the property that a procedure produces the result required by its specification for every valid input. An algorithm is not correct merely because it works on a few test cases. Its logic must be valid for the entire permitted input domain.

Specification

A specification defines what an algorithm is expected to do. It describes the permitted inputs, required outputs, assumptions, and relevant behavior. Correctness is evaluated by comparing the algorithm's actual behavior with this specification.

Partial Correctness

An algorithm is partially correct if, whenever it terminates after receiving a valid input, the result satisfies the required postcondition. Partial correctness alone does not guarantee that the algorithm terminates.

Termination

Termination means that the algorithm eventually completes. To establish total correctness for a terminating algorithm, it is necessary to establish both partial correctness and termination for every permitted input.

Preconditions

A precondition is a condition that must be true before an algorithm begins. For example, a binary search algorithm generally requires its input sequence to be sorted.

Postconditions

A postcondition is a condition that must be true after the algorithm completes successfully. For binary search, the postcondition states that the target is returned if it exists, or that its absence is correctly reported.

Hoare Logic

Hoare logic is a formal system for reasoning about program correctness. A Hoare triple has the form {P} C {Q}, where P is the precondition, C is a program or command, and Q is the postcondition. It expresses that if P holds and C terminates, then Q holds.

Loop Invariants

A loop invariant is a property that remains true before and after each iteration of a loop. It is used to reason about the correctness of iterative algorithms. A standard proof establishes initialization, maintenance, and termination.

Initialization

The initialization step proves that the invariant is true before the first loop iteration.

Maintenance

The maintenance step proves that if the invariant is true before an iteration, it remains true after that iteration.

Termination Proof

The termination step shows that the loop eventually ends and that the invariant, together with the termination condition, implies the desired postcondition.

Inductive Proof

Many algorithm correctness proofs use mathematical induction. The proof establishes a base case and then demonstrates that the property remains true when moving from one problem size to the next.

Testing Vs Proof

Testing checks an algorithm on selected inputs and is valuable for discovering defects. However, testing a finite collection of cases cannot generally prove correctness for an unlimited input domain. Formal proof provides a logical argument covering all inputs within the specification.

Variables

SymbolMeaningUnit

P

Precondition that must hold before execution.

Logical condition

C

Command or algorithm being analyzed.

Not applicable

Q

Postcondition expected after successful execution.

Logical condition

I

Loop invariant that remains true across loop iterations.

Logical property

Example or application

Title

Proving the Correctness of a Summation Algorithm

Problem

Calculate the sum of integers from 1 through n, where n is a positive integer.

Algorithm

Initialize total to zero, then add each integer from 1 to n.

Pseudocode

ALGORITHM SumToN(n)
total ← 0
FOR i ← 1 TO n DO
total ← total + i
END FOR
RETURN total
END ALGORITHM

Loop Invariant

Before the iteration for i begins, total = 1 + 2 + ... + (i - 1).

Proof

Initialization

Before the first iteration, i = 1 and total = 0. The sum of the integers from 1 through 0 is the empty sum, which equals zero. Therefore, the invariant holds.

Maintenance

Assume total contains the sum from 1 through i - 1. The algorithm adds i, so total becomes the sum from 1 through i. Thus, the invariant is preserved.

Termination

After the final iteration, i = n has been added. Therefore, total equals 1 + 2 + ... + n, which is the required result.

Result Formula

n(n + 1) / 2

Explanation

The invariant describes exactly what the accumulated total represents. Its initialization, maintenance, and termination establish that the returned result is correct.

Difficulty

Intermediate

Learning Objectives

  • Define algorithm correctness.

  • Distinguish partial correctness from total correctness.

  • Identify preconditions and postconditions.

  • Understand the purpose of Hoare triples.

  • Apply loop invariants to iterative algorithms.

  • Explain initialization, maintenance, and termination.

  • Distinguish testing from formal verification.

Prerequisites

  • Algorithm Fundamentals

  • Conditional statements and loops

  • Basic mathematical logic

  • Mathematical induction is helpful

Formal Notation

Hoare Triple

{P} C {Q}

Meaning

If precondition P holds before command C and C terminates, postcondition Q holds afterward.

Total Correctness

Total correctness = Partial correctness + Termination

Qualification

The Hoare triple describes partial correctness unless termination is separately established or a total-correctness framework is used.

Complexity

Time

O(n)

Space

O(1)

Explanation

The algorithm performs one addition for each integer from 1 through n and stores only the running total and loop variable.

Proof Techniques

  • Mathematical induction

  • Loop invariants

  • Precondition and postcondition reasoning

  • Proof by contradiction

  • Structural induction for recursive structures

Common Mistakes

  • Assuming that successful test cases prove correctness.

  • Ignoring the preconditions required by an algorithm.

  • Proving partial correctness without considering termination.

  • Using a loop invariant that does not describe the actual program state.

  • Failing to establish initialization, maintenance, and termination.

  • Confusing an algorithm's intended behavior with its actual behavior.

Related Concepts

  • Characteristics of a Good Algorithm

  • Algorithm Design and Problem-Solving

  • Algorithm Efficiency

  • Recursion and Mathematical Induction

  • Formal Verification

Practice Exercise

Question

Prove that a linear search algorithm returns the index of a target when it exists in an array, and reports absence otherwise.

Expected Approach

Define the loop invariant in terms of the elements already examined. Show that no occurrence has been skipped, establish maintenance after each comparison, and analyze the termination cases.

Learning Focus

  • Loop invariants

  • Partial correctness

  • Termination

  • Postconditions

Key Concepts

NameDescription

Core idea

The central focus of algorithm correctness is the capability described here: A study of algorithm correctness, explaining how an algorithm can be shown to satisfy its specification for every valid input through preconditions, postconditions, loop invariants, termination arguments, and formal reasoning.

Problem context

Algorithm Correctness is relevant when a computational task requires the behavior or capability described by this topic.

Correct use

Before using algorithm correctness, check its assumptions, input requirements, expected output, and resource constraints.

Applications

  • Designing and implementing solutions involving algorithm correctness.

  • Teaching and assessing algorithm correctness in computer-science courses and interviews.

  • Checking solutions that use algorithm correctness against correctness and resource constraints.

Limitations

  • The suitability of algorithm correctness depends on the exact problem requirements and the assumptions made about the input.

  • An implementation of algorithm correctness can fail if its boundary conditions, data representation, or required invariants are handled incorrectly.

  • For algorithm correctness, evaluate representative and unusually difficult inputs; a single small demonstration is not enough to establish reliability.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Thomas H. Cormen et al. — Introduction to Algorithms
  • Edsger W. Dijkstra — A Discipline of Programming
  • Robert W. Floyd — Assigning Meanings to Programs

Suggest a correction or source · More in Algorithms & Data Structures