An empirical estimation for time and memory algorithm complexities: newly developed R package

When an algorithm or a program runs on a computer, it requires some resources. The complexity of an algorithm is the measure of the resources, for some input. These complexities are usually space and time. The subject of the empirical computational complexity has been studied in the research. This article introduces GuessCompx which is an R package that performs an empirical estimation on the time and memory complexities of an algorithm or a function, and provides a reliable, convenient and simple procedure for estimation process. It tests multiple increasing-sizes samples of the user’s data and attempts to fit one of seven complexity functions: O(N), O(Nˆ2), O(log(N)), etc. In addition, based on the best fit procedure using leave one out-mean squared error (LOO-MSE), it predicts the full computation time and memory usage on the whole dataset. Together with this results, a plot and a significance test are returned. Complexity is assessed with regard to the user’s actual dataset through its size (and no other parameter). This article provides several examples demonstrating several cases (e.g., distance function, time series and custom function) and optimal parameters tuning.