Я думаю (не доказал, поэтому не уверен), что ваш вывод является верным утверждением, но на самом деле он не вытекает из вашей предпосылки. Если все, что вы знаете, это то, что деление двух n-значных чисел - это O (n ^ 2), все, что вы можете сделать из n- и m-значных чисел, - это то, что это O (max (n, m) ^ 2), не то чтобы это O (n * m). Это потому, что число из n цифр также может рассматриваться как число из n + 1 с ведущим 0, заменяя операцию на ту, с которой мы знаем сложность.
Например, который не является O (n m): используя длинное умножение, вычисление A ^ 2 + B ^ 2 равно O (n ^ 2), если A и B являются n-значными числами. Однако это не O (n m), если A - это n цифр, а B - это m цифр. Чтобы увидеть это, исправьте B = 1, следовательно, m = 1 и обратите внимание, что вычисление A ^ 2 + 1 с помощью длинного умножения определенно не является O (log (A)) [*].
Ваше «противоречие» не противоречит ни вашей предпосылке, ни вашему выводу. Нотация Big-O - это асимптотическое поведение, которое стремится к бесконечности. Тот факт, что f (3) = 12 для некоторой функции f абсолютно ничего не говорит о предельных значениях big-O для f. Даже если f (n) = 12 для всех нечетных n, это все равно ничего не говорит вам об оценках big-O, потому что вы не знаете, как быстро функция растет на четных числах. Наличие быстрых особых случаев не означает, что функция быстрая.
[] На самом деле, я сам там злоупотреблял нотацией. Если функция с двумя переменными f (n, m) равна O (n m), из этого не следует (как я предположил), что f (n, 1) равно O (n). Но из этого следует, что для достаточно большого m f (n, m) равно O (n), поэтому замените 1 на «некоторую большую постоянную или другую».