Верхние оценки трудоемкости первого алгоритма восстановления целых чисел.

Оценим трудоёмкость приведенных алгоритмов.

Лемма. Трудоемкость алгоритмов Mod1 и Mod2 не превосходит соответственно и .

Доказательство. Приведем трудоемкости шагов алгоритма Mod1. Будем считать, что длина числа равна количеству ячеек памяти, необходимых для его записи. В частности, длина каждого из модулей равна 1. Длина произведения не превосходит суммы длин сомножителей, поэтому длина не превосходит . Трудоемкость умножения (деления) числа длины на число длины 1 не превосходит . Следовательно, трудоемкость первого шага алгоритма Mod1 не превосходит величины . Аналогично, трудоёмкости четвертого и шестого шагов не превосходят . Трудоёмкость второго, третьего и седьмого шагов ограничена сверху константой. Пятый шаг заключается в вычисление остатка от деления на и затем решения сравнения с помощью расширенного алгоритма Евклида. Трудоемкость алгоритма Евклида для чисел помещающихся в ячейку памяти ограничена константой. Таким образом, трудоёмкость пятого шага определяется трудоёмкостью вычисления остатка, которая ограничена величиной . Шаги 3-7 повторяются раз. В результате трудоёмкость алгоритма Mod1 ограничена сверху .

Длина чисел не превосходит , поэтому трудоёмкость первого шага алгоритма Mod2 не больше . Длина числа сверху ограничена величиной . Операция деления на сводится к последовательному делению на модули , поэтому трудоёмкость второго шага алгоритма Mod2 не больше . Аналогично оценивается трудоемкость третьего шага. В результате, трудоемкость всего алгоритма не превосходит .