# what is the time complexity for binary division by repeated subtraction?

The divisor and dividend are of length n and m bits respectively.

According to Wikipedia article, https://en.wikipedia.org/wiki/Output-sensitive_algorithm division by substraction is an output sensitive algorithm and has the time complexity of Θ(Q). Can the time complexity be calculated in terms of length of input bits?

• What did you try? Where did you get stuck? It seems you already have enough information to answer the question yourself. – David Richerby Sep 23 '18 at 23:45

If you calculate Z = floor (X / Y) by repeated subtraction, then you will perform Z subtractions. If you divide exactly n bits by exactly m bits, then there are at least $$1/2 \cdot 2^{n-m}$$ and at most $$2 \cdot 2^{n-m}$$ subtractions, so it's $$\theta (2^{n-m})$$ subtractions.
If you divide at most 2 bits by at most m bits, then Y might be 1 and in the worst case there are almost $$2^n$$ subtractions, so $$O(2^n)$$ subtractions.