Abstract
Scalability is an important aspect of algorithm design. Typical methods for accessing scalability in terms of running time include theoretical time complexity by algorithm analysis, and model-fitting time complexity derived from simulation results. However, theoretical time complexity often fails to account for real-world conditions in algorithm implementation such as influence from compilers, and lacks a simulation-based examination method. Alternatively, model-fitting time complexity is prone to learn a model with incorrect scaling orders. Here, we propose the empirical time complexity (ETC), which is a data-driven model-free and parameter-free method to account for the factors influencing an algorithm; for instance, the crosstalk between algorithm realization, compilation and hardware implementation. This can be used to guide code optimization and to gain algorithmic maximum efficiency for specific hardware, programming language or compiler. The values of ETC in function of an input variable form a curve that offers a visual representation of how an algorithm scale with input size. When the ETC curves of different versions of an algorithm are reported together with the theoretical time complexity curve, their comparison allows to select what versions are closer to the theoretical complexity. To showcase the utility of ETC in real scenarios, we investigated two sets of algorithms (graph shortest path and matrix multiplication) and we offer evidence on how ETC is crucial for diagnostic and optimized design of algorithms as close as possible to their theoretical limit.

This publication has 11 references indexed in Scilit: