What would the Big O be? Can something like this be done in O(log(n)) where n is the number of bits?

  • 1
    $\begingroup$ Welcome to Computer Science! What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$ – Raphael Jul 6 '16 at 23:56
  • 1
    $\begingroup$ In particular, have you checked obvious candidates such as computing the GCD? $\endgroup$ – Raphael Jul 6 '16 at 23:58

Integer division

The best algorithm known for integer division has running time that is slightly more than linear, i.e., a bit more than $O(n)$. In particular, it is something like $O(n \lg n 2^{\Theta(\lg^* n}))$ (which is a bit faster than $O(n \lg n \lg \lg n)$. The time complexity of integer division is the same as the time complexity of integer multiplication. See https://en.wikipedia.org/wiki/Division_algorithm and https://en.wikipedia.org/wiki/Multiplication_algorithm.

Caution: these algorithms are purely theoretical. The constants hidden by the big-O notation make them impractical for most sizes you'll run into in real life. But there are plenty of other algorithms that are faster than the naive algorithm and are useful in practice.

No, you can't do it in $O(\lg n)$ time, where $n$ is the number of bits in the input: you obviously can't do it in less than $O(n)$ time, since it takes that much time just to read in the entire input.

Testing divisibility

The problem of testing divisibility could in theory be easier: it asks for just a yes-or-no answer (is $y$ divisible by $x$ or not?) instead of the result of the full division (compute $\lfloor y/x \rfloor$). Obviously, you can use any algorithm for integer division to test integer divisibility (with the same running time). I don't know if there is any faster way to test integer divisibility.

A conceptually simple way to test whether $y$ is divisible by $x$ is to check whether $y \bmod x$ is zero or not. However, I don't know of any way to compute the remainder $y \bmod x$ in linear time (in time linear in the number of bits of the input, i.e., in $O(n)$ time, where $n=\lg(x)+\lg(y)$). As before, you obviously can't do it in less than $O(n)$ time.

See also https://cstheory.stackexchange.com/q/16788/5038, which basically states the same thing: no faster algorithms are known, but no one has proven lower bounds ruling out the possibility of faster algorithms.

  • $\begingroup$ In fact, "you obviously can't do it in less than" Ω(n) time when the other integer is 3, for the same reason. ​ ​ ​ ​ $\endgroup$ – user12859 Jul 6 '16 at 19:46
  • $\begingroup$ Two n bit numbers can be multiplied on O (log n) steps - if you have unlimited hardware and design specific hardware for each n. $\endgroup$ – gnasher729 Jul 6 '16 at 22:55
  • 1
    $\begingroup$ @gnasher729, OK, fair enough. Well, I guess at that point we get to try to speculate about what the poster might have meant by "the Big O". I think if we're considering a special computation model (e.g., circuits where we only care about the depth of the circuit, hardware, parallel computation, ...), the burden is on the poster to specify the model of computation in their question. Or, you could write another answer about the complexity in some particular model of computation -- go for it! $\endgroup$ – D.W. Jul 6 '16 at 23:21

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.