Empirical Time Complexity for Assessing the Algorithm Computational Consumption on a Hardware
Preprint
- 29 January 2025
- preprint
- Published by MDPI AG in Preprints.org
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.Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- Artificial intelligence: A powerful paradigm for scientific researchThe Innovation, 2021
- Efficient hyperparameter optimization through model-based reinforcement learningNeurocomputing, 2020
- On the empirical scaling of running time for finding optimal solutions to the TSPJournal of Heuristics, 2018
- A nonuniform popularity-similarity optimization (nPSO) model to efficiently generate realistic complex networks with communitiesNew Journal of Physics, 2018
- A survey of machine learning for big data processingEURASIP Journal on Advances in Signal Processing, 2016
- On the empirical scaling of run-time for finding optimal solutions to the travelling salesman problemEuropean Journal of Operational Research, 2014
- Needed: An Empirical Science of AlgorithmsOperations Research, 1994
- An overview of computational complexityCommunications of the ACM, 1983
- Analysing the empirical time complexity of high-performance algorithms for SAT and TSP
- Gaussian elimination is not optimalNumerische Mathematik, 1969