I got 100%. This is the puzzle which I feel I had the least confidence, so I just tried whatever and see what happens.
In order to deal with the constant term in program initialization, I sought to calculate the derivative of the input data, so the constant term can be ignored. Then I compared the derivatives against the derivatives of the ideal curve.
To compare the derivates, I chose to divide one gradient against another, this leads to errors with the O(1) curve as the gradient is zero. I hard-coded this case checking if t hasnāt varied much then just output O(1).
Also calculating the curve of O(2^n) leads to overflow in all test cases except the last one due to large n as input. I added a check to ignore this curve when overflow happens.
I was happy that I needed not add any special handling beyond that - no need to cut / remove data or detect outliers.
I saw āregression analysisā as a note to this problem, so I calculated fitted values for various functions (least squares method, as it is usual in linear regression) and then residual sum of squares (RSS). Then I decided to choose a function with the least RSS. With this approach, I have problem only with the āsimpleā example, where the answer should be O(1).
It seems that regression analysis is not appropriate for the first example (I can find another functions with smaller RSS and therefore is more optimal from this point of view). I solved this problem separately with a ratio of the last and the first value (if it is small enough, then it is O(1) problem), otherwise I use regression to find a better function. Do you have some other way to recognize O(1) problem?
Thereās a typo in the problem description: āLetās determin the complexity of each algorithm and choose the most optimal one.ā where ādetermineā is misspelt.
This is an interesting find, and matches well with the theory. As n grows, the approximation by a constant multiplied with the reference fits better, because the fastest-growing component of the cost dominates more. In principle, trying to fit complexity measures to samples from small n is hoping for compliance in a region where it cannot be expected.
Nevertheless, my own current solution does exactly this, even overprioritizing the smaller nā¦
It does not have to be bounded by k*n^2 for all n either, as long as there exists a finite n after which it is bounded for all larger n. (I suppose an equivalent criterion could be formulated that also adds a constant to make the function bounded for all n.)
No need for the āLeast squaresā methodā¦ All functions basically starts at [0,0] (except O(1)) and you can simply tell what complexity is used just by looking at graph (average local growth)
Compute empirical orders of growth for log-log plot (didnāt quite get wikipedia, but first 3 minutes of this coursera video helped a lot)
Compute average value of that growth
TOP SECRET - observe what averages gives you
O(2^n) is the craziest that one is resolved without averaging, just looking at last entry of order of growth is enough
Actually you just need linear least squares here (you fit a non-linear model, but linear in terms of unknown parameters). At worst you have a 2x2 matrix to invert, otherwise only matrix / vector multiplications.
The only issue with O(1) comes from overfitting noised data with the additional regression parameter of the other complexity candidates. A penalty on parameter number does the trick.
I spent a few hours trying to wrap my head around the least squares method without success, so I tried computing the averages of the empirical orders of growth like you suggested, and I was able to solve the problem 100% in about 5 mins and less than 20 lines.
I took the approach of checking which test / f(num) of the possible output functions produced a dataset that was closest to a constant value, but had problems with the n^3 validator. Removing outlier test values (those that were most different from the average) got me to 100%, but required some tuning. Removing too many outliers would pass the n^3 validator but caused one of the others (n^2, IIRC) to fail.
Maybe the correct approach is to disregard all values outside some threshold of variance, like 1 standard deviation. Maybe the difference between n^2 and n^3 is really fine when compared to random variation for the range of n values provided.
Iām curious about what response my program was giving originally when failing validator n^3. Iām betting it was n^2.
log-log is really powerful !!! Thanks for the idea, no need for regression, really elegant!
I was using only (x1, y1) and (xn, yn) to calculate slope, but cannot pass validator O(n^3). Then, using the average slope solves the problem.
I guess maybe in the O(n^3) validator, beginning or ending part has lots of noise.
