https://stackoverflow.com/questions/23426543
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian
9 is explained as 4 reads (i, a[i], x, y), 3 operators (+, + and +)... but 2 writes don't make any sense.
If I were to count at this granularity level, it would be five reads (i twice - once to find a[i] in left side to write, once to find a[i] on the right side to read) and one write (the just mentioned a[i]). I'd also add two indexing operations (which are basically glorified addition operations) for the two [i].
Then there is the loop, which is basically i = 1; while(i <= n) .... i = i + 1; end while, so that's one assignment before loop, one comparison and one read at the top of the loop and one assignment, one read and one addition at the end of the loop (possibly an additional one each to load the constant, but the original slide ignored them, which is a valid choice, I suppose).
And "n for creating the array"... I don't believe that's how it works. Nulling an array does correspond to the array length; but just allocating it does not actually access the allocated memory. That a single-byte array will be much faster to null (or initialise) than a million-byte one is a fact, but the former is allocated just as fast as the latter, as long as there is available memory to do so (and as long as no janitorial duties need to be performed to do so). 2*n sounds like nonsense here.
However, none of that is actually ever useful. If you are measuring algorithm complexity, you never do it in this way - one operation is of the same complexity as seven, or a million. The thing that matters is how the number of operations grows when some external parameter (normally, size of data, usually symbolized by n) changes. This snippet is of complexity O(n), because the complexity grows at the same speed as the n grows. If you have two loops nested, it is noted as O(n^2), meaning that the rate the complexity scales is quadratic: the algorithm runs four times as long or takes four times the memory if the data just doubles. Whether the contents of the loop take one operation or million, or they take a millisecond or an hour, has no impact on algorithmic complexity. The only important thing in the slide for calculating the time complexity is the loop.
Well, kind of. Depending on what the data being manipulated is, the insides could have impact on algorithmic complexity of the whole. For example, multiplication is not actually a single operation; it has a non-n complexity of its own. But it is usually trivial and ignorable, because we normally operate on fixed-precision numbers; which makes multiplication a predictable and fixed complexity. If you can have numbers of arbitrary precision, a pair of two-digit numbers take much less to multiply than a pair of 1000-digit numbers, and if you have these then you need to take it into account. And obviously, if you call a function inside your loop that has a loop in it, it definitely has an impact on the complexity.
Another problem here is that the definition of a primitive operation is arbitrary. I already hinted at it before: loading a constant might be counted as a primitive operation, but here it isn't. If it is, x = 1 would also be two operations, not one as the slide shows. Indeed, in 8086 assembly, you have to write mov ax, 1; mov offset x, ax (load a 1 into a register, store a register to memory) (I might have messed up the syntax, it's been a while). However, x = x + 1, when optimised, is only one instruction in many microprocessors.
But if you're trying to optimise some time-critical piece of code in Assembly or microinstructions, you can't just bunch all the operations together. Each operation takes a specific length, and typically multiplication will take more than addition. Each cycle counts. Luckily, most of us never need to work at this low a level.
TL;DR: No-one counts operations in pseudo-code.
