I'm just starting a course on Computational Number Theory and have very little Computer Science background but definitely know enough about the big-O notation.

I currently have an assignment to work on:

An algorithm reads in the binary digits of a positive integer $N$ and determines whether $N$ is a multiple of 3. Show that the algorithm takes time at least of order $n$, where $n$ is the number of binary digits of $N$.

Basically, I have thought up of an algorithm which I'm pretty sure is correct: (I don't know what's the best/correct way to write an algorithm but here's my attempt)

  1. Start with a binary number $x=a_na_{n-1}\dots a_1a_0$.

  2. Then compute $x'=\sum^{i=n}_{i=0} (\frac{3}{2}+\frac{1}{2}(-1)^{i+1})a_i$.

  3. Then $x'=0 \mod3 \iff 3|x$

This works because $2^{2k}=1\mod3$ and $2^{2k+1}=2\mod3$

I can guess that my algorithm takes time at least of order $n$ because I need order $n$ steps to compute $x'$.

However, I have my doubts:

  1. How do I know my algorithm is the optimal algorithm?

  2. Am I 'cheating' by saying $x'=0 \mod3 \iff 3|x$?

  3. Am I even answering the question correctly by providing such an algorithm or is there some other sort of analysis to show lower bounds for algorithm time?

  • $\begingroup$ Note that you should usually restrict yourself to one question per port, but I think yours are reasonably scoped and can be dealt with in one answer. $\endgroup$ – Raphael May 5 '14 at 23:26
  • 1
    $\begingroup$ related Algorithms computing if a number is a multiple of 3 $\endgroup$ – Hendrik Jan May 5 '14 at 23:40
  • 1
    $\begingroup$ You can also think of it in this way: for binary numbers, each binary digit can influence the divisibility by 3. As such you have to "do something" with each digit, so at least N "somethings" for N digits. $\endgroup$ – PlasmaHH May 6 '14 at 9:44

If an algorithm that takes less than $O(n)$ time, this means that the algorithm won't be able to look at all the digits of the number. Thus you can prove a lower bound of $O(n)$ by showing that you have to look at all (or almost all) digits of the number in order to decide divisibility.

To show the latter property, assume you had an algorithm that decides divisibility by 3 by looking at $n-2$ or fewer of the digits. This gives you 2 digits that you can set freely, since the algorithm has to give the same answer for any choice of these digits (it doesn't look at them) and it has to be always correct. However you can show that no matter where these digits are and what the value of the remaining digits is, you always have a choice for the digits that gives a number divisible by 3 and another choice that doesn't. Thus, the assumed algorithm can not exist. (I'll leave it to you to show the existance of such choices.)

| cite | improve this answer | |
  • $\begingroup$ Why not $n-1$ though? $\endgroup$ – Haikal Yeo May 6 '14 at 9:59
  • 1
    $\begingroup$ There are situations, where you can flip a (specific) single bit without affecting divisibility by 3. E.g. for "10?" you can set the last bit (?) to either 0 or 1 and get a number not divisible by 3 both times. $\endgroup$ – FrankW May 6 '14 at 10:13
  • 1
    $\begingroup$ Yes, an algorithm that looked at $\frac n2$ digits would still be $O(n)$ (if it didn't do too much other stuff). But why should I prove a lower bound of $\frac n2$, if I can prove one of $n-2$? $\endgroup$ – FrankW May 6 '14 at 10:23
  • $\begingroup$ The same argument works in many cases: If you can prove that you cannot determine the correct result by looking at n-1 of n input items, then a lower bound for running time is O (n). And all you have to prove for this is that if I could change one item after you give the answer, I could turn your answer into a wrong one. Any other lower bounds are usually very, very difficult to prove. $\endgroup$ – gnasher729 Dec 16 '16 at 21:48

Answering your questions one by one:

  1. From what you know, you don't; you'd have to show that no algorithm can be better, that is it attains a (tight) lower bound.

  2. I don't know what you mean by "cheating". If it's valid, it's okay, unless you are not allowed to use the modulo operation.

    However, is it valid? What do you compute in step 2?

  3. No, not at all! Providing an algorithm with a certain runtime only proves an upper bound on the complexity of the solved problem. Lower bounds are tougher; there is no genereal method that I know of.

Some notes and hints that might get you on the right track:

  • You give very abstract pseudo code; it's level is often okay when communicating ideas of algorithms, but can get you in trouble when analysing runtime. There are many examples for more detailed ("lower level") pseudo code around, e.g. here.
  • Remember elementary school. Is there a simple property by which you can tell if a number is divisible by three?
  • Which cost model do you assume? The algorithm you give does take linear time in the uniform cost model, but not in the logarithmic model.
  • Towards a lower bound, assume a (deterministic) algorithm that solves the problem could do so without looking at all digits of the input number. What can you conclude?
| cite | improve this answer | |

Let's answer your questions one by one:

  1. You have a misunderstanding here. There is no clear notion of "the optimal algorithm", for two reasons. First, it depends on the exact computational model. Second, usually it is too much to expect to obtain the absolute optimal algorithm. Therefore we usually only worry about optimality up to multiplicative constants (big O), or if we want to be more careful, optimality up to lower order factors. In the first case, given an algorithm with running time $O(f(n))$, we would like a matching lower bound of $\Omega(f(n))$. In the second case, given an algorithm with running time $f(n)$, we would like a lower bound of $f(n) - o(f(n))$.

  2. You are totally cheating. You could just as well compute $x \pmod{3}$ at the outset. It is true that $x'$ is much smaller than $x$, but still it needn't be constant size. Moreover, even your addition in the second step of your algorithm is problematic since the summand gets bigger and bigger.

  3. Lower bounds are not shown by giving algorithms. (Unless in a very fancy way, like in Ryan Williams' recent work).

The standard way to compute the residue modulo 3 is as follows:

  1. Initialize $a$ to $0$.

  2. For $i$ from $0$ to $n$, compute $a \gets (a + x_i) \pmod{3}$. (You can implement this instruction using a table if you wish.)

This takes $O(n)$ time in any reasonable computation model (even a Turing machine, if you're very careful). There is also an equivalent way of stating this algorithm using finite automata, which amounts to the very same algorithm.

Lower bounds in general are very difficult, but here all we need to do is prove a linear lower bound, thus showing that the algorithm is optimal up to multiplicative constants. The trick is showing that the algorithm needs to read all the input bits. The reason is that $2^i \not\equiv 0 \pmod{3}$ for all $i$. I'll let you fill in the details. (The analysis become simpler if you allow leading zeroes).

| cite | improve this answer | |
  • $\begingroup$ I apologise for my misuse of the the phrase 'the optimal algorithm'. I was referring to the possibility that there may exist a faster (than linear) algorithm. I also agree that it is cheating and hence felt like I wasn't doing something right. But why does the second step of the algorithm become problematic? Isn't that just dependent on the $n$ terms and hence has running time $O(f(n))$? $\endgroup$ – Haikal Yeo May 6 '14 at 8:26
  • $\begingroup$ @HaikalYeo It depends on the machine model, but assuming that the machine model doesn't allow $O(1)$ operations on unbounded operands (otherwise you can compute the entire modulo in $O(1)$), then computing the sum takes more than linear time since one of the operands, the running sum, keeps growing and is super-constant. $\endgroup$ – Yuval Filmus May 6 '14 at 12:52

It is rather easy to construct a DFA that recognizes the language of binary strings divisible by 3. States are the residue classes modulo 3, your transition function is $\delta (q, d) = (2 \cdot q + d) \bmod 3$, initial and final state is 0.

The exact same construction works for other bases and divisors.

In any case, no algorithm can take less than $O(n)$, where $n$ is the length of the string; this is optimal.

| cite | improve this answer | |
  • $\begingroup$ How does one know that $O(n)$ is optimal for this problem? Is this a well-known result, or something that is obvious? $\endgroup$ – Guildenstern May 6 '14 at 1:17
  • $\begingroup$ @Guildenstern, the result depends on all bits (unlike, say, checking if it is divisible by 256). $\endgroup$ – vonbrand May 6 '14 at 1:26
  • $\begingroup$ @vonbrand: Specify that your program accepts input in base 3, with the tape positioned at the ones digit. Bingo--O(1). $\endgroup$ – supercat May 6 '14 at 2:01
  • 1
    $\begingroup$ @supercat, here the input is binary. $\endgroup$ – vonbrand May 6 '14 at 2:16

Actually you gave the answer yourself: since $2^{2k}=1\mod3$ and $2^{2k+1}=2\mod3$, one must consider all $n$ binary digits to check if the number is a multiple of $3$, there is no way around. Hence any algorithm is at least $O(n)$. This is the answer to the question, there is no need to provide an algorithm which is $O(n)$.

| cite | improve this answer | |
  • $\begingroup$ But this is dependent on the algorithm that I'm using right? How do I know that there is no faster (than linear) algorithm out there that doesn't use this property? $\endgroup$ – Haikal Yeo May 6 '14 at 8:23
  • $\begingroup$ This is not dependent on the algorithm you choose. Since every binary digit is either = 1 or = 2 mod 3, every single digit must be considered, as it can change the value of x mod 3. $\endgroup$ – Christofer Ohlsson May 6 '14 at 10:57

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.