Notations for algorithmic complexity in elementary operations

Question

I am comparing several algorithms (moments and matrix products) for real-time computing in terms of numerical complexity in elementary operations.

[EDIT] Algorithms are very similar in terms of loops and operations. All operations are performed in a scalar way (not matrix/vector product), with elements stored in lookup tables or computed on the fly. Let us say I want to check whether Algoritm 1 uses more operations that Algoritm 2. I will consider only additions (or subtractions), multiplies and non-integer exponentiations.

I have so far split the operations in three classes: sums/differences, products and non-integer powers: $(+,-)$, $(\times)$ and $(\hat{})$. I am not interested in asymptotics, e.g. I am not using the Landau symbol $O()$.

[EDIT] For instance, if Algorithm 1 and 2 have [$n^2$ $(+,-)$/$2n^2$ $(\times)$] and [$n^3$ $(+,-)$/$3n^2$ $(\times)$] respectively, may I say that Algorithm 1 is plausibly more efficient.

1. Are these three classes sufficient for a basic comparision, is it still meaningful to assume the same complexity for plus and minus?
2. Should I include a metric for loops, for instance? Or is it so very dependent on software/hardware that such algorithmic complexity is becoming worthless?
3. What would be a nice compact notation? For $a x^{0.3}+b y^{0.7}$, I am thinking about something like: $$(1_+,2_\times,2_{\hat{}})$$

Answer 1

The categories you use were meaningful a couple of decades ago when floating point operations were expensive compared to all other kinds of things processors did. But they are no longer: for example, floating point additions and multiplications today take only a few clock ticks and consequently not much longer than integer operations such as those you do when performing loop index increments or the jump at the beginning or end of a loop; and floating point operations take far less time than loading data from memory (by an order or magnitude or more), in particular if that data is not in a cache.

Consequently, the performance of algorithms can no longer be measured adequately using only the measures you count in your post. To give an example I have recently come across, my collaborator Martin Kronbichler measured the time it takes (or, rather, the memory bandwidth, which is the inverse, normalized by the amount of data) for simple operations such as the dot product between two vectors. If your measures were relevant, you'd get a constant line (because the number of operations per vector element is constant). But in reality, these curves are far from horizontal lines. Take a look here to see examples: https://github.com/dealii/dealii/pull/2517