What impact does the modulo operator have in a for-loop?

Question

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?

Answer 1

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$.