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.
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
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
instead of 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
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 algorithmfor (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
Note: If we want to learn how to prove the total correctness of an algorithm, we can visit here.
Free Resources
