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

возвести любое число в любую степень без особых вычислительных затрат
Пустая фраза. Обычно говорят о асимптотической сложности, зависящей от длины аргументов.

adjective Причем здесь асимптотическая сложность и длина аргументов. Все зависит от выбраного метода вычислений, а не о сложности вычисление определенным методом.

Ею меряются вычислительные затраты.

adjective Зачем считать асимптотисескую сложность, если общепринятым способом задача решается с помощью огромного, зависящего от самого выражения, количества действий, а второе решение позволяет получить такой же результат за небольшое количество более простых действий, количество которых не зависит от самих чисел.

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

adjective Во многих ситуациях ассимптотическая сложность неприменима, и если полагаться только на нее, то получишь ложные результаты.
Поэтому, когда я говорю "вычислительные затраты" я подразумеваю абстрактную оценку, выбор которой напрямую зависит от конкретной задачи. И если я говорю "вычислительные затраты меньше" то подразумеваю очевидность их разницы между приведеными примерами не зависимо от используемых оценок. Тем более я не ставил себе целью доказывать величину этих затрат!
Математический язык хорош для доказательств, но использование его без надобности не дает ничего.

Время вычисления напрямую связано с асимптотической сложностью. Арифметических операций, не зависящих от длины аргументов, в принципе быть не может. Самое быстрое -- O(N)

adjective В теории да, но не на практике!

adjective Ассимптотическая сложность это усредненый показатель и он может быть подсчитан если есть достаточно информации об объекте, но если мы об объекте знаем немного у нас есть шанс получить либо явное занижение либо завышение показателей.

Понятное дело, что точное выражение лучше асимптотического. А о каком алгоритме возведения в степень шла речь в 1-м комменте?