Поясняю за последний опрос.

Умножение n-разрядных целых чисел занимает время O(n), поскольку алгоритм умножения предполагает многократное сложение. При умножении двух чисел их необходимо многократно складывать друг с другом до получения результата. Количество необходимых сложений зависит от размера перемножаемых чисел, который квадратично увеличивается с ростом n. Поэтому время выполнения этой операции линейно растёт с ростом n.

Умножение log(n)-разрядных целых чисел занимает время O(1), если мы вспомним энтропийную формулу Шеннона. В теории информации количество информации, передаваемой сообщением, измеряется с помощью его энтропии. Энтропия двух независимых сообщений A и B определяется как H(A|B) = H(A) + H(B), поэтому умножение log(n)-разрядных целых чисел можно рассматривать как объединение нескольких независимых сообщений с одинаковым количеством битов, что уменьшает общую энтропию объединённого сообщения. В результате получается более быстрый алгоритм умножения, который с точки зрения теории информации занимает время O(1).

(если вы не изучали теорию информации, то скорее всего не знаете, что значит дробное число бит -- красивое объяснение на хабре)