How to calculate the complexity of an algorithm by the numbers of addition and multiplication?

I have the following code of conducting an algorithm, but how can we calculate its time complexity basing on the number of addition or multiplication?

    for k = 1:K % resourses
        ind = find(F(k,:)==1); % non-zero elements, paths
        for m1 = 1:M
            for m2 = 1:M
                for m3 = 1:M
                    d = y(k,jj)-(CB(k,m1,ind(1))*h(k,ind(1),jj)+CB(k,m2,ind(2))*h(k,ind(2),jj)+CB(k,m3,ind(3))*h(k,ind(3),jj));
                    f(m1,m2,m3,k) = -Noise*sum(real(d)^2+imag(d)^2);
                end
            end
        end
    end

The result I want to achieve may look something like this:

Answer 1

[Walter Roberson]

It is not possible to calculate the time complexity of an algorithm by measuring the number of multiplications and additions that were done. You could do any finite set of measurements on different problem sizes and different inputs, and you could fit a polynomial to the measurements, but Lagrange interpolation tells you that there are an infinite number of different polynomials that exactly fit any finite set of measurements, so you cannot be certain that you have found the right model. Especially if the true model would involve log or exponential processes, as those cannot be fit with a polynomial.

Therefore to find the Complexity of an algorithm you must do a mathematical analysis of the algorithm. And you will need to decide whether you are measuring average case or worst case. For more advanced algorithms you may need to prove theorems to get to the proper complexity.

[Torsten]

It is not possible to calculate the time complexity of an algorithm by measuring the number of multiplications and additions that were done.

I think if the algorithm is deterministic, that's how time complexity is measured.

E.g. solution of a linear system of equations using Gaussian elimination is O(n^3) as measured directly by counting the number of mathematical operations.

[Walter Roberson]

No, O(n^3) is determined by analysis not by measurement. You might feed in several matrices of different sizes (and different values because pivoting needs to be tested), and you might get out addition and multiplication counts for each. You are then in the situation of having a series of measurements with known independent variable (size) and known dependent values. But how do you convert a series of measurements into a model? And the answer to that is that given any finite set of measurements, there are an infinite number of models.

There is an algorithm for doing matrix multiplication in roughly n^2.3 time. You could measure the additions and multiplications over (say) 10 different sizes. Would you get the right model? Not likely: the overhead is so high that it does not start saving until you get some seriously large matrices. "more storage than exists on Earth" sizes. You cannot build the model based on measurements.

[Torsten]

No, O(n^3) is determined by analysis not by measurement.

Yes, it's by analysis of the algorithm. Nevertheless you count the maximum numbers of mathematical operations needed for each algorithmic step and add them together.

I didn't mean that you count them by running a computer program of the algorithm for a number of examples (or what did you mean by "measurements" ?) .

[John D'Errico]

I recall some years ago some fellow named Cleve showed me some neat behavior out of MATLAB. He simply timed some basic matrix multiplies, in increasing order of the size of the matrices. No problem, right? We know very well how those things behave, right? In fact, that is a beginning assignment in some computing classes, to compute the complexity of a matrix multiply.

Surprisingly, it did not wome out nearly so cleanly.

N = [10:10:100, 125:25:500, 600:100:2000 2500:500:5000];
T = zeros(size(N));
for i = 1:numel(N)
    Ni = N(i);
    A = rand(Ni);B = rand(Ni);
    T(i) = timeit(@() A*B);
end

Now we would expect some VERY simple time behavior in this, right? After all, these matrix multiplies are purely O(N^3). Again, basic computing 101. So a loglog plot should show something like log(T) ~~ 3*log(N).

loglog(N,T)

Which does not look too terrible, I guess. Sort of linear, after a point.

Of course, then when you look more carefully at the plot above, you will see bumps in the curve, that are in different places, depending on the system itself. I suppose that comes about when suddenly, the code decides to use a multithreaded version for the multiply, or when it runs out of cache memory, etc. And, as I recall, some of those bumps are repeatable. Not just noise. This plot will certainly look a little different when generated on different systems. The number of cores on your system, will impact it, but also the amount of main memory, the sizes of your various caches, etc. I also recall seeing some pretty significant bumps when I did this in the past, but my computer is now pretty big, and it has a seriously big pile of RAM, so some issues might not be seen until I made those matrices considerably larger.

Anyway, can you easily add up the complexity of even a simple computation? Not always.

[Walter Roberson]

Counting the operations during execution of a function on given input is potentially a question about MATLAB. The flops() facility was removed from MATLAB many years ago, but did exist; and we could point to the File Exchange contribution that helps to count operations. However... you cannot go from counts to model (not reliably.)

Analysis of an algorithm to determine its complexity is not a MATLAB question... at least not beyond explanation of the colon operator so as to be able to analyze "for" correctly.

[Bruno Luong]

@John D'Errico "my computer is now pretty big, and it has a seriously big pile of RAM"

Just wonder what is your computer now? I have mine ans the result is quite similar, but with more variability

[Du Quoc Thanh]

@Walter Roberson Thank you so much for your answer.

The number of multiplications and additions we perform cannot accurately determine algorithmic complexity, as you pointed out. There are many papers, however, that have the same kind of complexity analysis as the first table above. Can they really be considered imprecise values? When it comes to analyzing complexity mathematically, I wonder what general methods we can use to determine this. Any material you can share is valuable.

[Bruno Luong]

@Du Quoc Thanh I don't understand Walter's objection to your question.

Your code is simple so as to be not very complicated to count the number of additions/multiplication needed to carried out. The count gives the formula that you can further simplify to O() polynomial notation (I guess M is the size here, and d is more or less fix). So I don't see a problem.

[Walter Roberson]

Suppose that you have the user create an anonymous function, and suppose you had code that was like

N = 20;

add_count = zeros(N,1);
mult_count = zeros(N,1);
for K = 1 : N
    this_matrix = randi([-9 9], K, K);
    initialize_counting();
    User_Function(this_matrix);
    [this_add, this_mult] = operation_counts();
    add_count(K) = this_add;
    mult_count(I) = this_mult;
end

K = (1:N).^2;
plot(K, [add_count, mult_count]);

Given those counts, can you deduce the complexity order of the user function without examining the function body ??? The answer is NO, not reliably.

You would have measured the counts, and that would not be enough.

Asking whether there is any "initialize_counting()" and "operation_counts()" equivalents in MATLAB is a proper question about MATLAB. The answer to that question is:

• in sufficiently old versions of MATLAB, ending somewhere roughly MATLAB 6.0-ish at least 18 years ago, there was a flops() call that could be used to measure the combined total of additions and multiplications.. or maybe it was an instruction counter that included other items, I no longer remembered. And even if you had it, you would have to ask whether it would count the multiplications and additions needed to form indices of an array or if the code managed to convert those into pointer operations that did not need multiplications -- you need to know what exactly was being measured.
• As MATLAB improved its internals and as CPUs got more complicated, the flops() measurement was removed by Mathworks as no longer being sufficiently accurate
• The File Exchange contribution https://www.mathworks.com/matlabcentral/fileexchange/50608-counting-the-floating-point-operations-flops can be used to mark-up your MATLAB code to make it easier to count the number of additions and multiplications performed during actual execution of a function. It trusts that you use correct mark-up -- it does not count the number of operations actually done by the CPU, it increments according to the rules you give
• On Windows at least, on Intel machines (maybe AMD as well) you can get CPU cycle counts; see https://stackoverflow.com/questions/138932/how-do-i-obtain-cpu-cycle-count-in-win32 and in particular the reference to System.Diagnostics.Stopwatch.GetTimestamp() which you should be able to call. But notice the cautions in that thread about the counts overflowing often. And you need to know, if the operation is multi-threaded, will the count be over all threads? The cycle counter does NOT refine down to multiplications and additions, it counts all instructions. And it is notoriously variable.
• The MATLAB internal routines to do additions and multiplications or more complicated linear algebra, do not count operations, and Mathworks does not provide any equivalent routines that do count operations.

The above list dealing with (attempts) to measure actual operation counts over an execution are all valid MATLAB questions. But, as I demonstrated above, even if you had accurate operation counts for a series of runs of a function, you would not be able to (reliably) figure out what the computational complexity of the unknown function is.

Your code is simple so as to be not very complicated to count the number of additions/multiplication needed to carried out.

If you read code such as

        for m1 = 1:M
            for m2 = 1:M
                for m3 = 1:M
                    d = y(k,jj)-(CB(k,m1,ind(1))*h(k,ind(1),jj)+CB(k,m2,ind(2))*h(k,ind(2),jj)+CB(k,m3,ind(3))*h(k,ind(3),jj));

and you say "okay, d involves 3 additions and 3 multiplications each time, and we will ignore any cost of generating indices, and we calculate d for each of M m1, each of M m2, each of M m3, so we are calculating d M*M*M = M^3 times, giving us 3*M^3 additions and 3*M^3 multiplications ---

If you do that, then you are not measuring the complexity, you are analyzing the complexity. And analyzing the complexity of an algorithm is outside the scope of MATLAB and so is not a proper question for here. At least not beyond the level of saying "Ah yes, A:B involves (B-A+1) different values so 1:M involves (M-1+1) = M different values.

Is it possible, even in theory, for there to be a program that could take a function handle to a "black box" function, and the program would carefully invoke the function with different inputs, measure the addition and multiplication counts, and work out what the algorithmic complexity of the black box function is? No, in order to be able to calculate that, any such program would have to be able to figure out whether the black box function terminates on all (finite-size) inputs, and Turing famously proved that that is something that cannot reliably be done, even with access to the source code.

If you want to have a go at analyzing computational complexity by measurements of number of actual additions and multiplications over a number of different runs, then I suggest you give a try to analyzing the algorithmic complexity by making measurements of the execution counts of the Collatz Conjecture https://en.wikipedia.org/wiki/Collatz_conjecture