educative.io

Educative

Why is the number of primitive ops for sum += 1 equal to three?

should we be looking at only “basic” operation amounts or “primitive operation” when solving for an equation for time complexity with respect to n?

Hello Eloy
The terms “basic” operations and “primitive” operations mean the same thing. Think of these as operations that can be performed by a hypothetical processor in one clock cycle, two clock cycles, or any constant number of clock cycles. Reading from a memory location into a processor register, writing to a memory location from a register and adding the values in two registers while saving the result in another register are all primitive operations.
So, sum += 1 involves:

  1. Reading the current value of the variable sum from memory to a register, say, register A

  2. Adding the constant 1 to the contents of register A, saving the result to register B

  3. Saving the contents of register B back to the memory location allocated for the variable sum

That is why we say that sum += 1 involves three primitive operations. I’m sure you are aware that, eventually, when we talk about asymptotic notation, the significance of the constants diminishes. So, even if you said sum += 1 involves two primitive operations, it would not be a serious mistake, in the long run. Please note that I have said “diminished” and not “vanished”. Leading constants are sometimes important even in asymptotic analysis, but that is an entirely different discussion.
Hope this helps.

1 Like