liveBook · Manning

Correctness

As explained in Algorithms Every Programmer Should Know

The property of producing results that satisfy the specified requirements for all applicable inputs and conditions.

An algorithm is correct when it produces the expected answer for the specified problem across its inputs, within the required time. Correctness is a basic quality to consider alongside verifiability and ease of implementation. section 1.2 section 1.2.1

Sorting the same numbers

Insertion sort, bubble sort, and selection sort use different steps but produce the same sorted output. Their efficiency can differ; correctness is about producing the expected answer, not being the fastest. section 1.2 section 1.2.1

How Algorithms Every Programmer Should Know covers it

How deep it goes
Defines correctness as a quality of algorithms but does not develop formal verification or proofs.
Examples
Compares insertion sort, bubble sort, and selection sort as different methods that produce the same sorted output.
What it assumes
Assumes a specified problem and expected output, while introducing algorithms as steps for solving problems.
What you can do after
Evaluate algorithm choices by distinguishing correct results from efficiency and other constraints.
How it connects
Ties correctness to algorithms, sorting, efficiency, and tradeoffs among time, memory, cost, and scale.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.