codemode's blog

How does the modulo operation affects the time complexity of a program ?
By codemode, history, 5 years ago, In English

Say, I have an O(n^2) or O(n^3) solution to a problem . If I use the modulo operator in most of the statements inside the loops, will my program slow down ? With which factor will it slow down ? like 2*x,3*x,.. ? (if "x" is the execution time of the program when no modulo is used)

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +17 Vote: I do not like it

It will be a few times slower. Just implement anything and check yourself.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I was doing Longest Divisible Subset Problem. In that I did it by two approaches.

    (1) Sorted the array and then applied a%b once (2) Didnt sort the array and applied a%b and b%a to check twice.

    I got higher execution time in 2nd scenario, though I expected it should be in 1st as I am sorting the array that takes O(nlogn) while modulo operators take O(1) I suppose.

    Why did this happen?

    Please reply and help me out Mr. Legend!

    Would be so happy if you reply as I am your huge fan!

    Love from India!

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      Modulo operations are slow, that's the reason. Running time and complexity aren't the same thing.

      → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

The modulo operation does not affect the time complexity at all. It's a constant time operation just like other basic arithmetic operators. However, the time complexity isn't equal to the actual runtime, which will depend on many factors such as how good your implementation is.

The modulo operation may be slower than other basic operations, but if you blindly replace them with branches such as if statements you might actually slow your program down since an unpredictable branch can be slower than a modulo operation in my experience. In the end, there's no single number that will always predict how much modulo operations slow down your program. It all depends on many factors such as your implementation and your compiler. The only way to know for sure is to try it out and measure the execution time.

For more on branch prediction, see https://stackoverflow.com/a/11227902/9254539

I wanted to write some code to show you modulo vs predictable branch vs unpredictable branch, but I can't reliably prevent the compiler from obliterating my benchmark by optimizing the whole thing out.

→ Reply
»
4 years ago, # |
  Vote: I like it -12 Vote: I do not like it

you can feel of it when you see my submission in 1st every thing is same except I used modulo for every iteration which gives me straight TLE

and then when I don't apply in each iteration it takes 62 ms

bad code 111795934

good code 111799139

→ Reply