Это именно теория сложности, она занимается не только очень сложными задачами.
Вычисление времени выполнения
для конкретной вычислительной машины неинтересно в силу необщности результата. Других подходов я не слышал.
Ладно, допустим предъявлены два алгоритма
и
(пусть деление на ноль не рассматривается как проблема). Существует ли универсальное доказательство, что первый алгоритм эффективнее? Можно как-то задать ограничения для чисел
. Ну и важное: кроме этих чисел ничего не дано, нет готовых
и
.
Наверное доказательство вполне простое - нужно просто посчитать количество эквивалентных операций в обоих алгоритмах и понять, что во втором алгоритме их столько же, но там есть еще лишние операции.
То есть сравнительный подход существует, но для этого нужно предъявить искомый алгоритм целиком и эталонный алгоритм.
если разрешается использовать только арифметические операции
Да, понятно, но в частный случай уходить неинтересно. Интересно лишь для примера.