Here's an example of what I mean:

def complexity(n):
    count = 0
    for x in range(1, n+1):
        for y in range(1, (n*n)+1):
            if y % n == 0:
                for z in range(1, n+1):
                    count += 1
    return count

The first for loop is of course θ(n), the second one θ(n^2). But what impact does the modulo operator have? And what would then be the complexity of the whole thing?


It feels like you're trying to think in terms of pre-defined recipes, rather than just figuring it out by reasoning about the situation. The if statement triggers every time $y$ is a multiple of $n$. So just work out how many different values in $\{1, \dots, n^2+1\}$ are multiples of $n$, and that's how many times the innermost for loop runs.

Of course, your code is just an example but, in real life, with something as simple and predictable as the modulo operator, you wouldn't use this approach of "generate every possible value of $y$ and see which ones pass the test". It's much more efficient to just write a for loop that directly assigns the values $n, 2n, \dots, n^2$ to $y$.

  • 1
    $\begingroup$ If I understand correctly, OP is asking about the complexity of the modulo operator $\endgroup$ – gire Jun 18 '19 at 8:39
  • $\begingroup$ @gire I can't say that you're wrong, but if I wanted to know the complexity of the modulo operator, I'd just ask that, and I wouldn't wrap it in for loops, and I wouldn't ask about it's "impact" on those loops. In any case, mod has the same complexity as multiplication: Wikipedia says you can compute $x^a\bmod y$ in time $M(n)2^k$, where $x$ and $y$ have $n$ bits, $a$ has $k$ bits and $M(n)$ is the cost of multiplying two $n$-bit numbers. Take $a=k=1$ and you get $x\bmod y$. $\endgroup$ – David Richerby Jun 18 '19 at 9:30

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.