How is schoolbook long division an O(n^2) algorithm?
- by eSKay
Premise:
This Wikipedia page suggests that
the computational complexity of
Schoolbook long division is
O(n^2).
Deduction:
Instead of taking "Two n-digit
numbers", if I take one n-digit number
and one m-digit number, then the
complexity would be O(n*m).
Contradiction:
Suppose you divide 100000000 (n
digits) by 1000 (m…