Analysis of Complexity of Some Combinatorial Algorithms Using Halstead Metrics and Time Measures

Bashar Bin Usman^1, , Ibrahim Abdullahi¹ and Okeyinka Aderemi Elisha¹

¹Department of Computer Science, Faculty of Natural Sciences, Ibrahim Badamasi Babangida University, Lapai, Niger State, Nigeria

Cite this paper:
Bashar Bin Usman, Ibrahim Abdullahi and Okeyinka Aderemi Elisha. Analysis of Complexity of Some Combinatorial Algorithms Using Halstead Metrics and Time Measures. American Journal of Applied Mathematics and Statistics. 2024; 12(3):66-69. doi: 10.12691/ajams-12-3-4

Abstract

The Knapsack problem is a combinatorial optimization problem for which finding an exact solution using exhaustive search methods is impractical. Therefore, approximate algorithms are usually considered when tackling this optimization problem. The goal of this study was to analyze the complexity of the Knapsack problem using three approximate algorithms: greedy, dynamic programming, and branch-and-bound methods. To achieve this, we measured the Halstead metrics and computational time complexity of these three algorithms. Our methodology involved solving a hypothetical Knapsack problem using the three algorithms in the same programming environment. Experiments were conducted with varying input datasets, and the time complexities of the algorithms were recorded for each experiment. The average time complexities were computed at the end of the experiments. Additionally, we calculated the Halstead metrics required for the study. Both the Halstead metrics and computational time metrics for the three algorithms were then compared. Our findings showed that the greedy approach was the most efficient heuristic, followed closely by the dynamic programming method, with the branch-and-bound algorithm being the least efficient. Future work will incorporate real-world data with specific item characteristics to enhance the relevance and applicability of the findings. Additionally, it will explore hybrid approaches that combine these algorithms to leverage their respective strengths and effectively address their weaknesses.

Keywords:
heuristics complexity knapsack problem greedy branch-and-bound dynamic programming halstead metrics

This work is licensed under a Creative Commons Attribution 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/

References:

[1]	Elizabeth L. How the Mathematical Conundrum Called the ‘Knapsack Problem Is All Around Us. https:// www.smithsonianmag.com/science-nature/ why-knapsack-problem- all-around-us-180974333/ 2020; search on 25/09/23.
[2]	Ingariola, G, & Korsh, J. A general algorithm for one dimensional knapsack problems, Operation Research 1973;25(5). Friedrich T. and Neumann F. What’s hot in evolutionary computation, Conference on Artificial Intelligence (AAAI), 2017;5064–5066.
[3]	Vala J, Monaka D, Pandya J. Comparative Analysis of Dynamic and Greedy Approaches for Dynamic Programming. Int J Mod Trends Eng Res. 2014; 5.
[4]	Omotosho O. I. & Okeyinka A.E., (2015). Comparative analysis of the greedy method and dynamic programming in solving the knapsack problem. Global Journal of Advanced Engineering Technologies and Sciences .
[5]	Ameen S, & Azzam S. Comparing between different approaches to solve the 0/1 Knapsack problem. IJCSNS International Journal of Computer Science and Network Security, 16(7), 2016.
[6]	Sampurno GI, Endang S, & Alamsyah. Comparison of Dynamic Programming Algorithm and Greedy Algorithm on Integer Knapsack Problem in Freight Transportation. Scientific Journal of Informatics 2018; Vol. 5, No. 1; p-ISSN 2407-7658.
[7]	Namer AA, Fatimah TA. 0/1 knapsack problem: greedy vs. dynamic-programming. International Journal of Advanced Engineering and Management Research 2020; 5(02).
[8]	Chen X. A Comparison of Greedy Algorithm and Dynamic Programming Algorithm. doi.org 2022; Saerch 12/09/2022.
[9]	Oluyinka IO, Okeyinka AE. Comparative analysis of the greedy method and dynamic programming in solving the knapsack problem. Global Journal of Advanced Engineering Technologies and Sciences. 2015.