Пусть трудоемкость умножения целых чисел длины s и l равна 
. Тогда трудоемкость вычисления 
по формуле 
, с последующим округлением в 
разрядах по порядку определяется величиной О( 
). Общая трудоемкость метода Ньютона не превосходит по порядку О 
.
Приведем оценку трудоемкости операции деления методом Ньютона в предположении, что умножение проводится с использованием быстрого преобразования Фурье. В этом случае 
и вычисление лучше вести по формуле 
. При этом, образы 
, 
вычисляются сразу. Потом над ними проводятся соответствующие операции умножения, вычитания, и только после этого восстанавливается результат. Поскольку 
, то длина произведения 
не превосходит 2k-1+1+n. Таким образом, трудоемкость k-ой итерации деления по порядку не превосходит О 
, а, значит, трудоемкость всего метода ограничена сверху величиной О 
O(m log m log (m-n)).
Тем самым доказана
Теорема. Трудоемкость деления чисел с остатком ограничена сверху величиной O(m log m log (m-n)).
