What is the correctness of an algorithm?

Overview

In this Answer, we demonstrate the correctness of an algorithm, the different types of correctness, and how empirical analysis is used to find faults in an algorithm.

Correctness

It is important for an algorithm to be correct. What does this actually mean? A correct algorithm always produces the expected output or follows the ground truth for the range of valid inputs and, eventually, terminates.

Why is it important?

An algorithm must be correct because we rely upon it for our desired output.

Types

There are two types of correctness: partial correctness and total correctness.

Types of correctness

Partial correctness

An algorithm is partially correct if it receives valid input and then terminates.

We can prove the partial correctness of an algorithm through empirical analysisThe practice of using empirical methods to study the behavior of algorithms or tests on a few cases.

Let's consider the following example. In order for our program to find the max number from an array of integers, it gives the correct answers on positive numbers only. So, what if the array has negative numbers, or a mixture of both negative and positive numbers? Our program will not give us the correct answer in these cases. Therefore, the algorithm in the given example is partially correct because it only works in a few cases.

#include <iostream>
using namespace std;
int main() {
  int numbers[4] = {13, 4, 24, 7};
  int maxNum = -1;
for (int i = 0; i < sizeof(numbers)/ sizeof(int); i++) { 
  if (numbers[i] > maxNum) {
    maxNum = numbers[i];
  }
}
cout << maxNum;
}

Note: We get the correct answer because all numbers in the array are positive, and greater than the number we initialized.

#include <iostream>
using namespace std;
int main() {
  int numbers[4] = {-13, -4, -24, -7};
  int maxNum = -1;
for (int i = 0; i < sizeof(numbers)/ sizeof(int); i++) { 
  if (numbers[i] > maxNum) {
    maxNum = numbers[i];
  }
}
cout << maxNum;
}

Note: Now, the program returns −1-1 instead of −4-4 because it does not find anything greater than the number we initialized.

Total correctness

An algorithm is totally correct if it receives valid input, terminates, and always returns the correct output.

We can prove this by formal reasoning or mathematically, for instance, with a proof by inductionA proof by induction is just like an ordinary proof, in which every step must be justified..

Let's convert the previous example into total correctness by tweaking our algorithm. Now, the program always gives the correct answer, even if the array contains negative integers, or a mixture of positive and negative.

#include <iostream>
using namespace std;
int main() {
  int numbers[4] = {13, -4, 24, -7};
  int maxNum = numbers[0];  // Change in the previous algorithm
for (int i = 0; i < sizeof(numbers)/ sizeof(int); i++) { 
  if (numbers[i] > maxNum) {
    maxNum = numbers[i];
  }
}
cout << maxNum;
}

Previously, we compared a whole array with a fixed number −1-1. This gave us incorrect answers because if an array is of negative numbers, it never finds a number larger than −1-1 itself. So, once we make our algorithm correct in every possible case, it follows total correctness.

Note: If we want to learn how to prove the total correctness of an algorithm, we can visit here.

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved