performance-testingperformance-estimation

Computational complexity for a specific data


If complexity is O(nlog2(n))... How to prove execution time for data like 10e7if we know that for data like 10e5execution time is 0.1s?


Solution

  • In short: To my knowledge, you don't prove it in this way.

    More verbosely:
    The thing about complexity is that they are reported in Big O notation, in which any constants and lower order terms are discarded. For example; the complexity in the question O(nlog2(n)), however this could be the simplified form of k1 * n * log(k2 * log(k3 * n + c3) + c2) + c1.

    These constants cover things like initialization tasks which take the same time regardless of the number of samples, the proportional time it takes to do the log2(n) bit (each one of those could potentially take 10^6 times longer than the n bit), and so on.

    In addition to the constants you also have variable factors, such as the hardware on which the algorithm is executed, any additional load on the system, etc.

    In order use this as the basis for an estimate of execution time you would need to have enough samples of execution times with respect to problem sizes to estimate the both the constants and variable factors.

    For practical purposes one could gather multiple samples of execution times for a sufficiently sizable set of problem sizes, then fit the data with a suitable function based on your complexity formula.

    In terms of proving an execution time... not really doable, the best you can hope for is a best fit model and a significant p-value.

    Of course, if all you want is a rough guess you could always try assuming that all the constants and variables are 1 or 0 as appropriate and plug in the numbers you have: (0.1s / (10^5 * log2(10^5))) * (10^7 * log2(10^7)) = 11 ish