# Notations for algorithmic complexity in elementary operations

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{}})$$
• In addition to what Wolfgang says in his answer, if you just go by the instruction latencies and throughputs listed at software.intel.com/sites/landingpage/IntrinsicsGuide, it is incorrect to group multiplication and division together: the cost of one multiplication is basically the same as an addition, whereas a division is noticeably more expensive. – Kirill May 2 '16 at 22:59