Пусть у первого числа цифр, у второго . Если второй множитель длиннее первого, поменяем их местами по переместительному свойству умножения: произведение не изменится. Поэтому для оценки можно считать . По правилу умножения столбиком каждую из цифр второго множителя надо поочерёдно умножить на каждую из цифр первого. Получаем однозначных умножений для одной строки частичного произведения и всего таких умножений.
Затем частичных произведений складывают с учётом сдвига разрядов. Любое промежуточное произведение содержит не более цифр. При последовательном добавлении каждой из строк требуется не более порядка разрядных сложений, включая переносы. Поэтому их общее число не превосходит порядка . Так как , получаем . Значит, сложения также укладываются в оценку .
Например, при и нужно умножений цифр, чтобы получить две строки частичных произведений, а потом сложить эти строки. Если оба множителя имеют вдвое больше цифр, число пар цифр возрастает в четыре раза: .
Поэтому основная часть работы пропорциональна произведению длин записи: сложность алгоритма — . Точное число элементарных действий зависит от того, считать ли переносы и записи цифр отдельными шагами.
