> но это не критерий оценки временной сложности алгоритма.

O(n) не изменится, но throughput просядет в пару раз.

> корректность алгоритма с точным результатом или его "быстрота" с неточным результатом?

Так тут как бы выбор между ошибкой в runtime и неточным результатом. Хотя слово неточный не уместно, результат то точный и детерминированный, просто не тот который ожидается при конкретной математической операции.  

Вот допустим есть ошибка с переполнением, у нас есть тесты но они не покрыли конкретный случай вызывающий переполнение. Программа ушла клиентам или на сервер и в случае проверок на переполнение мы получим ошибку при определенных входных данных, это ошибка возникнет в момент исполнения.  
Конечно круто что мы ее перехватим, ведь вместо неправильного результата у нас программа просто не позволит пойти дальше, мы не запишем в базу неправильное значение и т.д. Но цена этому будет производительность, например в случае сервера наш сервер будет обслуживать в два раза меньше клиентов.

А если у нас не x86 архитектура, а какой-нибудь сервер на RISC-V где никаких флагов о переполнении в его ALU нет совсем, поту для него будут генерировать не 3 ассемблерные инструкции,  а 5-10, на таких CPU производительность просядет в 5-10 раз.