Towards Complexity Analysis of Some Combinatorial Algorithms Using Knapsack Model

Knapsack problem is a combinatorial optimisation problem which is concerned with finding a solution where an exhaustive search is difficult or even impractical to do. Approximate algorithms, also called heuristics are therefore applied in solving Knapsack problems. The goal of this study was to solve the Knapsack model using three heuristics viz: greedy, dynamic programming, and branch-and-bound strategies. The ultimate objective of our study was to evaluate the time complexities of these heuristics as input sizes become larger. In the bid to get that done, a Knapsack problem was solved using the approximate algorithms, employing the same programming environment, with varying input sizes. The problem was simulated using different input data sizes. A synthesis of the results obtained, that is, the various time complexities, was then carried out and a comparative study of the three algorithms was done. The coefficients of the variables used in the Knapsack model for simulation were generated using random numbers generating algorithm. Our results showed that the greedy algorithm was the most efficient computationally. The second best efficient was the dynamic progranmming algorithm while the least in terms of time complexity is branch-and-bound strategy. It is considered a worthwhile effort to study more metrics of complexity measurement. This is recommended as good enough for further research attention. However, our present study has shown in pragmatic form the computational complexity of the greedy, dynamic programming, and branch-and-bound algorithms.