4

I know this may be really basic, but I am unsure of the complexity of this procedure in Python:

def modten(n):

   return n%10

edit: It is done with Python. That is the only additional information provided for this question. The question asks to specify the order of growth

nicole
  • 744
  • 1
    The answer may depend on the implementation, which you have not specified. – Bill Dubuque Jul 23 '14 at 19:51
  • Considering that we can do arithmetic operations with any number of bits, the complexity of modten is O(1). Else, if it depends on the number of bits then it should depend on the implementation indeed. – aghost Jul 23 '14 at 19:54
  • 1
    This question appears in MIT's 6.00.1x p-set 6, problem 4-1. The question there is referring to the complexity in practice, i.e. in Python with $ n < 10^{10000} $. – Zaz Feb 23 '17 at 13:28

2 Answers2

3

If $n$ is represented as a bit string, then $n$ mod $10$ can be computed in time $O(\log n)$ (which is presumably what you meant when you wrote $O(n)$, i.e., you were calling $n$ is the number of bits of the parameter $n$, because otherwise complexity $O(n)$ would be absurdly large). Indeed, one can compute $n$ mod $10$ using a deterministic finite automaton with $10$ states, which is defined if $n$ is read starting from the big end, by having a transition from state $k$ to state $2k$ upon reading a $0$ and $k$ to $2k+1$ upon reading a $1$, where states are labeled mod $10$ (e.g., from state $6$ we move to state $2$ or $3$ according as we read a $0$ or $1$), and finally returning the final state after all bits are read. Obviously, this is done in linear time, i.e., $O(\log n)$.

The answer $O(\log n\, \log\log n)$ would be plausible if the parameter $10$ were not kept fixed and $n$ stands for the max of the two inputs (although I'm not sure we know how to do division that quickly; $O(\log n\, (\log\log n)^2)$ is more like it).

Gro-Tsen
  • 5,541
  • if it is done in linear time, then would that not be O(1)? – nicole Jul 23 '14 at 20:08
  • @DonaldJenkins132: No, $O(1)$ is constant time. Very little can be done that way, because you can't even read all the digits of input. Checking whether a binary number $n$ is even, however, is doable in constant time (just look at the last bit). – Gro-Tsen Jul 23 '14 at 21:14
  • Then linear time is O(n)? – nicole Jul 23 '14 at 21:23
  • It depends what you call $n$. Normally we use $n$ to denote the number of bits of input, so linear time is indeed $O(n)$, but since you called your input parameter $n$, I can't also call $n$ the number of bits of $n$! So I call it $\log n$ (logically), and "linear time" is $O(\log n)$. – Gro-Tsen Jul 23 '14 at 22:06
1

Using computer primitive types (say 64-bit long and double) the algorithm should be at least as fast as this: 

return n - 10*floor(n / 10)

Wich performs $4 = \mathcal O(1)$ operations (divide, floor, multiply, subtract).

According to this it uses an algorithm wich is (according to the accepted answer) $\mathcal O(\log n)$ (proportional to the product of the length ($\sim\log$) of the two numbers). The comments, however, claim $\mathcal O(n^2)$ (wich is a lot worse).

Community
  • 1
AlexR
  • 24,905