Does anyone of you know how to associate an algorithm execution time (of experimental execution) to a well known complexity time? For example, say a divide and conquer algorithm lasts theoretically O(nlognn^2) or (nlogn), in a theoretical way, doing reccurence ecuations and all that stuff. But when you plot the data from a CSV, you can't say just by looking at it 'oh yea this is O(n^2).The data from the CSV is like:n, execution_time_for_that_n...How can I use a regression method to derive O-classes from such data?
Getting O-bounds by applying regression methods to execution time measurements
algorithm analysis;asymptotics;runtime analysis;experimental analysis
It's impossible. No finite set of measurements can prove asymptotic bounds.Proof sketch: Assume you had such a method. Apply it to any algorithm $A$. If your largest measurement is for input size $n_0$, construct a new algorithm $B$ that branches into $A$ for all $n \leq n_0$, and one with a different $\Theta$-runtime class for $n > n_0$. The method fails for $B$.That said, there are ways to perform reasonable experiments (for average-case performance). I recommend the book A Guide to Experimental Algorithmics by C. McGeoch.