3
$\begingroup$

Hi I have an algorithm for which I would like to provide the total runtime:

def foo(x):     s = []     if(len(x)%2 != 0):         return false     else:         for i in range(len(x)/2):           //some more operations         return true 

The loop is in O(n/2) but what is O() of the modulus operation? I guess it is does not matter much for the overall runtime of the Algorithm, but I would really like to know.

  • 1
    You seem to be only worried about the remainder on division by $2$. That costs nothing (OK, constant).2012-04-16
  • 0
    No my algorithm shall only iterate over the first half of the input so it should only accept inputs of even length. That's why I do the check with mod 22012-04-16
  • 0
    I was just pointing out that checking parity is dirt cheap. The general question about evaluating $x\%m$ efficiently for large $m$ is interesting, and much more difficult.2012-04-16

4 Answers 4