0
$\begingroup$

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?

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.