Time Complexity of Population-Based Metaheuristics

  • Mahamed G Omran Computer Science Department, Gulf University for Science & Technology, Kuwait
  • Andries Engelbrecht Department of Industrial Engineering and Computer Science Division, Stellenbosch University, South Africa
Keywords: Metaheuristics, Optimization, Time Complexity, Time Efficiency, Big-Oh, Big-Theta


This paper is a brief guide aimed at evaluating the time complexity of metaheuristic algorithms both mathematically and empirically. Starting with the mathematical foundational principles of time complexity analysis, key notations and fundamental concepts necessary for computing the time efficiency of a metaheuristic are introduced. The paper then applies these principles on three well-known metaheuristics, i.e. differential evolution, harmony search and the firefly algorithm. A procedure for the empirical analysis of metaheuristics' time efficiency is then presented. The procedure is then used to empirically analyze the computational cost of the three aforementioned metaheuristics. The pros and cons of the two approaches, i.e. mathematical and empirical analysis, are discussed.


Chartrand, G., and Zhang, P. Discrete Mathematics. Waveland Press, Inc., 2011.

Chopard, B., and Tomassini, M. An Introduction to Metaheuristics for Optimization. Springer, 2018.

Engelbrecht, A. Computational Intelligence: An Introduction, 2 ed. Wiley, 2007.

Gritli, H., Dubey, M., Kumar, V., Kaur, M., and Dao, T.-P. A systematic review on harmony search algorithm: Theory, literature, and applications. Mathematical Problems in Engineering (2021).

Kim, J. H. Harmony search algorithm: A unique music-inspired algorithm. Procedia Engineering 154 (2016), 1401–1405. 12th International Conference on Hydroinformatics (HIC 2016) - Smart

Water for the Future.

Levitin, A. Introduction to the Design and Analysis of Algorithms, 3 ed. Pearson, 2011.

Liben-Nowell, D. Connecting Discrete Mathematics and Computer Science, 2 ed. Cambridge University Press, 2022.

McConnell, J. Analysis of Algorithms: An Active Learning Approach, 2 ed. Jones and Bartlett Publishers, 2008.

Rouggarden, T. Algorithms Illuminated: Omnibus Edition, 1 ed. SOUNDLIKEYOURSELF PUBLISHING, 2022.

Storn, R., and Price, K. Differential evolution-a simple and efficient adaptive scheme for global optimization over continuous spaces. Technical report, Berkeley: ICSI, 1995.

Suman, B., and Kumar, P. A survey of simulated annealing as a tool for single and multiobjective optimization. Journal of the Operational Research Society 57, 10 (2021), 1143–1160.

Tanabe, R., and Fukunaga, A. Improving the search performance of SHADE using linear population size reduction. In Congress on Evolutionary Computation (CEC) (2014), IEEE, pp. 1658–1665.

Yang, X.-S. Nature-inspired optimization algorithms. Elsevier, 2014.

How to Cite
Omran, M. and Engelbrecht, A. 2023. Time Complexity of Population-Based Metaheuristics. MENDEL. 29, 2 (Dec. 2023), 255-260. DOI:https://doi.org/10.13164/mendel.2023.2.255.
Reviews & Analysis