Eso depende de su definición de relación de aproximación. Normalmente, la relación de aproximación se define como la peor relación entre la solución óptima y la producida por su algoritmo. Si este es el caso, todo lo que necesita para demostrar que la relación es ajustada es un mal ejemplo.
A veces, sin embargo, demuestra algo como . Esto significa que su relación de aproximación es realmente . Para demostrar que esto es estricto, necesitará un ejemplo para infinitos tamaños (pero no necesariamente para un tamaño genérico ; quizás todos sus ejemplos tengan un tamaño par).ALG≤2OPT+12+o(1)