It depends on what you consider an operation, doesn't it?
Exactly. I see far too many people lately who want to point out the technically correct (a.k.a. best kind of correct) version of algorithmic complexity where e.g. multiplication is not constant time. Often this is paired with the contrasting complexity analyses having different meanings for the N in the big O notation, e.g. bit complexity of input vs. number of elements input. Note, this is not the case above, but is often what I see happen. It's very sloppy to directly compare the two as they are making wildly different assumptions on what is constant time. The model matters. An example used in a parallel computing class I took was that comparison based sorting on P parallel processors could be done in log N time (less than the Nlog(N) lower bound of comparison based sorting) in the PRAM model where memory access across parallel processors is still O(1).
Comments
Exactly. I see far too many people lately who want to point out the technically correct (a.k.a. best kind of correct) version of algorithmic complexity where e.g. multiplication is not constant time. Often this is paired with the contrasting complexity analyses having different meanings for the N in the big O notation, e.g. bit complexity of input vs. number of elements input. Note, this is not the case above, but is often what I see happen. It's very sloppy to directly compare the two as they are making wildly different assumptions on what is constant time. The model matters. An example used in a parallel computing class I took was that comparison based sorting on P parallel processors could be done in log N time (less than the Nlog(N) lower bound of comparison based sorting) in the PRAM model where memory access across parallel processors is still O(1).