My favourite algorithm textbook: The Algorithm Design Manual S. Skiena.pdf had this interesting problem:
1-28. [5] Write a function to perform integer division without using either the / or * operators. Find a fast way to do it.
What's the lower bound for asymptotic complexity of this problem? `
P.S: I know repeated subtraction with a
will work. It has asymptotic linear complexity with b
(case where a = 1
). However, repeated subtraction has exponential complexity with $n$ where $n$ is the number of bits needed to represent the number. Specifically it is $\Theta(2^n)$. So it is definitely not fast.