Asymptotic and Computational Complexity of Algorithms and Program Performance

The paper considers software performance optimization technologies. It examines algorithm characteristics (asymptotic complexity and computational complexity) and the performance of algorithms implemented as programs. Profiling technology is used to optimize program performance. The given description of modern computing architectures shows that a processor and RAM resources cannot be fully taken into account when analyzing using asymptotic and computational complexity. Several examples demonstrate the limited possibilities of optimization using asymptotic and computational complexity. For the given examples, it is shown that using information about the capabilities of the architecture on which the program is executed allows for performance optimization without using low-level commands. Computational experiments were conducted on x86-64 (Intel Core) and ARM (Apple M1) platforms. The paper proposes a methodology for optimizing the performance of developed programs.

Keywords

asymptotic complexity; computational complexity; central processor; random access memory; performance; computing platform.

References

1. Slavin O.A. Software Performance Optimization for Classification and Linking of Administrative Documents. Programming and Computer Software, 2024, vol. 50, pp. 457-466. DOI: 10.1134/S0361768824700324
2. Trusov A., Limonova E., Nikolaev D., Arlazarov V.V. 4.6-Bit Quantization for Fast and Accurate Neural Network Inference on CPUs. Mathematics, 2024, vol. 12, no. 5, pp. 651. DOI: 10.3390/math12050651
3. Sher A., Trusov A., Limonova E., Nikolaev D., Arlazarov V.V. Neuron-by-Neuron Quantization for Efficient Low-Bit QNN Training. Mathematics, 2023, vol. 11, no. 9, pp. 2112. DOI: 10.3390/math11092112
4. Williams R. Faster All-Pairs Shortest Paths via Circuit Complexity. SIAM Journal on Computing, 2018, vol. 47, no. 5, pp. 1965-1985. DOI: 10.1137/15M1024524
5. Abboud A., Williams V.V. Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems. 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, 2014, pp. 434-443. DOI: 10.1109/FOCS.2014.53
6. Holm J., de Lichtenberg K., Thorup M. Poly-Logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge, and Biconnectivity. Journal of the Association for Computing Machinery, 2001, vol. 48, no. 4, pp. 723-760. DOI: 10.1145/276698.276715
7. Knuth D.E. The Art of Computer Programming. Fundamental Algorithms, Third Edition, 1997, vol. 1.
8. Razborov A. Foundations of Computational Complexity Theory. Surveys in Modern Mathematics, London Mathematical Society Lecture Note Series, 2005, vol. 321, pp. 186-202.
9. Klee V., Minty G.J. How Good is the Simplex Algorithm? Inequalities III, Academic Press, New York, 1972, pp. 159-175.
10. Khachiyan L. A Polynomial Algorithm in Linear Programming. Soviet Mathematics Doklady, 1979, vol. 20, pp. 191-194.
11. Bringmann K. Why Walking the Dog Takes Time: Frechet Distance Has No Strongly Subquadratic Algorithms Unless SETH Fails. 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, 2014, pp. 661-670. DOI: 10.1109/FOCS.2014.76
12. Alman J., Williams V.V. A Refined Laser Method and Faster Matrix Multiplication. 61st IEEE Symposium on Foundations of Computer Science, 2020. DOI: 10.48550/arXiv.2010.05846
13. Shenmaier V. On the Complexity of the Geometric Median Problem with Outliers. arXiv: Computer Science. Computational Geometry, 2021. DOI: 10.48550/arXiv.2112.00519
14. Woodruff D.P. Sketching as a Tool for Numerical Linear Algebra. Foundations and Trends in Theoretical Computer Science, 2014, vol. 10, no. 1-2, pp. 1-157. DOI: 10.1561/0400000060
15. Backurs A., Indyk P. Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False). SIAM Journal on Computing, 2018, vol. 47, no. 3, pp. 1087-1097. DOI: 10.1137/15M1053128
16. Egunov V.A., Kravets A.A. The New Method for Automatic Vectorization Efficiency Increasing. Springer. Cyber-Physical Systems: Data Science, Modelling and Software Optimization, 2024, pp. 195-208. DOI: 10.1007/978-3-031-67685-7_14
17. Intel\textsuperscript\textregistered VTune\textsuperscriptTM Profiler Performance Analysis Cookbook, https://www.intel.com/content/www/us/en/docs/vtune-profiler/cookbook/2023-2/overview.html (аccessed on 23.04.2025).
18. Alwan E.H., Ketran R.M., Hussein I.A. A Comprehensive Survey on Loop Unrolling Technique In Code Optimization. Journal of University of Babylon for Pure and Applied Sciences, 2024, vol. 32, no. 1, pp. 108-117. DOI: 10.29196/8cw3s787
19. Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. Introduction to Algorithms, 3rd Edition. MIT Press, 2009.
20. Egunov V.A., Kravets A.A. The Method for Increasing the Software Efficiency for Computing Systems with a Hierarchical Memory Structure. Cyber-Physical Systems Engineering and Control: Studies in Systems, Decision and Control, 2023, pp. 221-231. DOI: 10.1007/978-3-031-33159-6_17