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

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$$.
• @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$. – David Richerby Jun 18 at 9:30