Analyzing Time and Space Complexity: Kadane vs. Divide and Conquer Algorithms for Maximum Sub-array Problem
| Autor: | ISTIONO Wirawan |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2023 |
| Předmět: | |
| Zdroj: | Journal of Applied Computer Science & Mathematics, Vol 17, Iss 2, Pp 27-32 (2023) |
| Druh dokumentu: | article |
| ISSN: | 2066-4273 2066-3129 |
| DOI: | 10.4316/JACSM.202302004 |
| Popis: | The Kadane's Algorithm and Divide and Conquer algorithm share a commonality in their utilization, which is the ability to compute the maximum sum of a subarray within an array and determine which subarray holds that maximum sum. To accomplish this, it requires time to traverse the data one by one through its indices and depends on the length of the array. The longer the array, the longer it takes to traverse. Therefore, the objective of this research is to compare the performance of both algorithms in terms of how fast they traverse (Time Efficiency), sum the elements, determine the subarray that yields the maximum sum from the original array, and assess the amount of memory or space utilized by these algorithms (space complexity). By attempting several scenarios, where in the first scenario all values in the array sequence are positive, while in the second scenario, the array elements contain both positive and negative values, and in the third scenario, all values in the array sequence are negative, a comparison was made between the Kadane's algorithm and the Divide and Conquer algorithm. The conducted comparison revealed that Kadane's algorithm, in terms of time complexity, is faster than the Divide and Conquer algorithm, with an average speed of 7.04ms, and an average space complexity of 12.28. |
| Databáze: | Directory of Open Access Journals |
| Externí odkaz: |
|