| Paper title: |
Analyzing Time and Space Complexity: Kadane vs. Divide and Conquer Algorithms for Maximum Sub-array Problem |
| DOI: | https://doi.org/10.4316/JACSM.202302004 |
| Published in: | Issue 2, (Vol. 17) / 2023 |
| Publishing date: | 2023-10-16 |
| Pages: | 27-32 |
| Author(s): | ISTIONO Wirawan |
| Abstract. | 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 |
| Keywords: | Kadane Algorithm, Divide And Conquer, Subarray, Subarray Addition |
| References: | H. Tamaki and T. Tokuyama, “Algorithms for the maximum subarray problem based on matrix multiplication,” Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, no. January 1998, pp. 446–452, 1998, doi: 10.4036/iis.2000.99. 2. S. J. Weddell, T. Read, M. Thaher, and T. Takaoka, “Maximum subarray algorithms for use in astronomical imaging,” Journal of Electronic Imaging, vol. 22, no. 4, p. 043011, 2013, doi: 10.1117/1.jei.22.4.043011. 3. S. E. Bae and T. Takaoka, “Improved algorithms for the K-maximum subarray problem,” Computer Journal, vol. 49, no. 3, pp. 358–374, 2006, doi: 10.1093/comjnl/bxl007. 4. S. E. Bae and T. Takaoka, “A sub-cubic time algorithm for the k-maximum subarray problem,” Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4835 LNCS, pp. 751–762, 2007, doi: 10.1007/978-3-540-77120-3_65. 5. S. E. Bae and T. Takaoka, “Algorithm for K disjoint maximum subarrays,” Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3991 LNCS-I, pp. 595–602, 2006, doi: 10.1007/11758501_80. 6. T. Takaoka, “Efficient parallel algorithms for the maximum subarray problem,” Conferences in Research and Practice in Information Technology Series, vol. 152, no. January, pp. 45–50, 2014. 7. I. F. Araujo, D. K. Park, F. Petruccione, and A. J. da Silva, “A divide-and-conquer algorithm for quantum state preparation,” Scientific Reports, vol. 11, no. 1, pp. 1–12, 2021, doi: 10.1038/s41598-021-85474-1. 8. O. Cre, Z. Mathe, V. Lucia, C. Grama, A. Darabant, and L. Gorog, “A Hardware Implementation of the Kadane ’ s Algorithm for the Maximum Subsequence Problem,” in Conference: The 5th European Symposium on Biomedical Engineering, 2006, pp. 1–4. 9. L. Wang, J. Zhang, O. Wang, Z. Lin, and H. Lu, “SDC-Depth : Semantic Divide-and-Conquer Network for Monocular Depth Estimation,” in Conference: 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2020, pp. 541–550. doi: 10.1109/CVPR42600.2020.00062. 10. M. Thaher and T. Takaoka, “An efficient algorithm for the k maximum convex sums,” Procedia Computer Science, vol. 1, no. 1, pp. 1475–1483, 2010, doi: 10.1016/j.procs.2010.04.163. 11. S. Näher and D. Schmitt, “A framework for multi-core implementations of divide and conquer algorithms and its application to the convex hull problem,” Proceedings of the 20th Annual Canadian Conference on Computational Geometry, CCCG 2008, no. January 2008, pp. 203–206, 2008. 12. T. F. Zhao et al., “Evolutionary Divide-and-Conquer Algorithm for Virus Spreading Control over Networks,” IEEE Transactions on Cybernetics, vol. 51, no. 7, pp. 3752–3766, 2021, doi: 10.1109/TCYB.2020.2975530. 13. A. For, “A DIVIDE-AND-CONQUER ALGORITHM FOR THE BIDIAGONAL SVD,” Society for Industrial and Applied Mathematics, vol. 16, no. 1, pp. 79–92, 1995. 14. M. Yi, L. Xiaodong, Y. Xin, and M. N. Omidvar, “A competitive divide-and-conquer algorithm for unconstrained large-scale black-box optimization,” ACM Transactions on Mathematical Software, vol. 42, no. 2, pp. 1–24, 2016, doi: 10.1145/2791291. |
| Back to the journal content | |
