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 digits), you get 100000, which takes six steps to
arrive at.
Now, if you divide 100000000 (n
digits) by 10000 (m digits), you get 10000 . Now this takes only five steps.
Conclusion:
So, it seems that the order of
computation should be something like
O(n/m).
Question:
Who is wrong, me or Wikipedia, and
where?
