In Complexity Analysis why is ++ considered to be 2 operations?

StackOverflow https://stackoverflow.com/questions/443423

Question

In my Computer Science II class, the professor considers ++,--,*=, etc. to be 2 operations. However, at the Assembly level this is not really two operations. Can someone explain or is this just for the sake of simplicity?

Was it helpful?

Solution

I'd actually consider it to be 3 operations: read, increment (or whatever), write. That's assuming it's reading from some sort of shared memory into some sort of local storage (e.g. register or stack), operating on the local storage, then writing back.

How many operations it is at assembly level will depend on what you're incrementing, the platform, the hardware etc.

OTHER TIPS

Because ++ (ex: b++) is a simplification of 

b = b + 1

There are two operations there, the addition (b + 1) and then the assignment of the value of the addition to the original variable.

Why bother when doing complexity analysis? It is just O(1) :-)

EDIT: Please let me know why when you vote it down. Since the question is tagged complexity, I assume big O notion is the most important, rather than the actual constants. Besides, as already mentioned in other answers, how many operations this is depends on a lot of factors: the way you count operations, platform, compiler, etc.

I am gonna throw a few guesses.

  • Is your professor is referring to interpreted languages?
  • ++i is different than i++ maybe he's referring to that?

  • Maybe his assembly lang of choice needs the intermediate storage variable?

    add reg_temp, reg_i, 1
mov reg_i, reg_temp

Isn't it an addition plus a setter?

Similar to i+=1?

The prof is probably just referring to having to take the value, add 1 to it and then assign it back to the variable.

At the assembly level everything is done in registers so having a variable in A

ADD AX,1

However, in compiled languages everything has to be stored so i++ becomes (in pseudo assembly)

MOV AX,i
ADD AX, 1
MOV i, AX

Which is three operations...Unless I have forgotten my basic architecture completely...

You reminded me of a Kinda "Jury is not out" problem that I heard a long time ago.

"Preincrement is faster than postincrement"

I just did a quick google search.

  1. Lots of people still hold that as true.
  2. Others contend that Compilers are so optimized, the comparative high level code code can't be benchmarked.
  3. Yet other people contend that there is no difference.

It should be more than 2 in my opinion since it has two meanings depending on context and I always have to remind myself of them when I see it.

a = b++ is the same as a = b; b = b + 1

and

a = ++b is the same as b = b + 1; a = b

This is enough of a confusion to send most first year students off the cliff.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top