Hola,

Un algoritmo se dice que es Correctness, cuando el algoritmo es correcto respecto a unas especificaciones.

Si el grado de correlación entre los requerimientos que deben cumplirse y el resultado que se obtiene del algoritmo (tras introducirle unos valores de entrada), es siempre el mismo o el esperado (según las especificaciones) y se cumple para otros casos, entonces se habla de Total Correctness.

En cambio, si sólo te preocupa que tras unos valores de entrada, la respuesta que obtengas sea correcta (es decir, que independientemente de los datos de entrada, tu algoritmo funcione bien), entonces se habla de Partial Correctness.

Para entenderlo mejor, un ejemplo:

Estás buscando sucesivamente en una lista de números enteros (1,2,3...) para ver si puedes encontrar un número primo perfecto. Tú puedes escribir un programa que utilice un algoritmo (Partial Correctness) que vaya dividiendo por dos y comprobar si es perfecto o no. En principio, se podría obtener un valor correcto, o esperado según las espeficaciones que conocemos, y nuestro algoritmo funcionaría. Pero no se puede afirmar que es Total Correctness, porque los números primos perfectos, son todavía desconocidos. Es decir, no se conocen todas las especificaciones necesarias para que un algoritmo pueda determinar de manera totalmente cierta si un número entero es un número primo perfecto o no, y por tanto, al no existir una especificación completa (sino parcial), el algoritmo de este ejemplo no es Total Correctness

FUENTE: - Wikipedia ( aquí )

NOTA: - Es una traducción parcial por mi parte, puede contener errores de interpretación, pero al menos he entendido así el tema.