How to identify algorithm time complexity?

Hi everyone,

For identifing time complexity of an algorithm, at the last step as code on Matlab, I added power law fit method.

According to the results, how can i identify that this algorithm is for example: linear, logarithmic and so on.

Which value (b, c) do i need to consider as parameter?

[Torsten]

I've never heard that you can measure time complexity for an algorithm that is not guaranteed to stop like "fitting" (at least if the fitting is nonlinear). Where did you read about this ?

[Walter Roberson]

@Torsten

For some non-deterministic algorithms, it is possible to measure the best-case timing, the worst-case timing, and the average-case timing. Calculation of the average-case timing is often difficult.

But I think the user is saying that they have already measured the time of several runs, and has done a power-law fit over the results, and is now asking us how to interpreted the power-law parameters as indicating "linear", "log" and so-on.

Answer 1

[John D'Errico]

It is not at all trivial to determine the time complexity for SOME algorithms, at least not from merely knowing the method employed. But I think from your question you want to learn how to identify the time complexity from sampled times, to then infer an O(n^k) estimate of the time complexity. This will NOT be exact of course. That is not possible to do. I'm sorry, but it is not. However, you can do your best. I'll give an example of how this might work on an interesng problem, that is, what is the time complexity for the multiplication of large numbers, using syms?

First, generate a time sequence...

n = [300:50:1000,1100:100:2000,2500:500:20000,22500:2500:150000,160000:10000:400000];

I'm going to generate pairs of random integers, with n binary bits, convert them to LARGE scale symbolic integers, then multiply them. I'll time how long the miultiply takes, then use this to estimate the behavior of an integer m ultiply as the size of the integer grows very large. Note that an integer with 250000 bits would have roughly 83000 decimal digits.

T = NaN(size(n));
for i = 1:numel(n)
  ni = n(i);
  B1 = randbin(ni);
  D1 = sym(['0b',B1]);
  B2 = randbin(ni); % I've attached randbin to this answer
  D2 = sym(['0b',B2]);
  T(i) = timeit(@() D1*D2);
end

Now, if we assume this relationship is of the general form:

T(n) = a*n^b

then if we log the expression, we have:

log(T(n)) = log(a) + b*log(n))

Do you see that the model is now linear? So we should be able to estimate b, the long term order of that behavior, using just polyfit. A problem is, all sorts of crap happens for "small" values of n. So we need to go out far enough that the long term behavior is exposed. We will see when that starts to happen, by noting when the loglog plot approaches linearity.

loglog(n,T)

I'll guess it starts to linearize out around 1e4 for n, maybe a little larger. Below that point, other algorithms may be employed. And for small values of n, there will be other overhead that simply hides the large scale behavior.

k = n > 1e4;
loglog(n(k),T(k))

Note that things have not truly settled down, even at n = 10000, As well, there is some other interesting crap happening up higher, but it does not change the essential behavior we are looking to model. Sometimes we find the algorithm used changes. Sometimes there are issues happening with memory, or cache, etc. I would note that the plot looks sightly different when run on my own CPU, versus the CPU used by Answers MATLAB. This is not uncommon, since my personal CPU will have very different RAM and levels of cache available.

k = n > 3e4;
loglog(n(k),T(k))

I'll use fit here, because I like the way it also shows confidence bands arouund the parameters.

p1 = fit(log(n(k))',log(T(k))','poly1')

p1 = 
     Linear model Poly1:
     p1(x) = p1*x + p2
     Coefficients (with 95% confidence bounds):
       p1 =       1.251  (1.225, 1.277)
       p2 =       -20.5  (-20.81, -20.19)

p1(1) is the exponent we care about here. It expresses that long term behavior.

plot(p1,log(n(k))',log(T(k))')

Anyway, this suggests the order of a large scale integer multiply seems to be roughly O(n^1.25). (I would point out this is actually pretty impressive.) The bumps/breaks in the curve may well occur at changes in algorithm.

In the end, I want to note the importance of discarding the low end data here when I fit that model. I would also add that on my machine, the same code shows slightly different behavior:

k = n > 3e4;
loglog(n(k),T(k))
p1 = fit(log(n(k))',log(T(k))','poly1')

p1 = 

Linear model Poly1:
p1(x) = p1*x + p2
Coefficients (with 95% confidence bounds):
p1 =       1.402  (1.387, 1.416)
p2 =      -22.49  (-22.66, -22.32)

And I found a slope of roughly 1.4, suggesting the behavior is O(n^1.4), when the same test was performed on my CPU.

What is the true behavior for the scalar multiply of large symbolic number in MATLAB? That is hard to know to be absolutely certain. Again, it is likely to find a break, where different algorithms might be used for larger versus smaller numbers. Odds are, they probably use tools like a variation of Karatsuba, or Shonhage-Strassen.

https://en.wikipedia.org/wiki/Multiplication_algorithm

As far as knowing if an algorithm is inherantly linear versus logarithmic, etc., agin, this is a complex problem to solve. For that, you really need to understand the algorithm itself. A sorting algorithm, for example, can be analyzed to know the behavior. (Knuth is probably the bible here.)

[Walter Roberson]

It is not at all trivial to determine the time complexity for SOME algorithms

As an example: the time to reach "1" in the sequence of the Collatz Conjecture https://en.wikipedia.org/wiki/Collatz_conjecture is completely unknown. It is decidedly non-linear at the best of times, and although the conjecture has been extensively tested, no-one has been able to prove that it is true.