Minimum average case time complexity for sorting algorithms
Tóm tắt
There are certainly many sorting algorithms in this modern world of Computers, most of which work in second-order time and some in linearithmic time, but none have achieved more than that. There is none. However, is it even possible to hit the bottom more than that? The minimal temporal complexity that an ordering modus operandi may achieve goes in the order of
$$O(n\log _2n)$$
, without considering any modifications to the generalized computer architecture, according to a rigorous mathematical analysis presented in this paper. However, we have also taken into account the average time complexities of the algorithms to disperse throughout the smallest potential time complexity that a sorting algorithm may achieve. Three different search algorithms, namely, Binary, Interpolation, and Jump search, have been used in this article. The interpolation search takes less time if the array’s items are arranged in arithmetic progression, and there are many more similar biased situations where a certain approach produces superior results. Sorting algorithms have been proposed herewith, with Searching Techniques as intermediate. The Computational Complexity of the Sorting Algorithm amalgamated with Interpolation Search as an Intermediate Step is compared with Sorting Algorithms amalgamated with Jump Search, Binary Search as an intermediate.
Tài liệu tham khảo
Ahmed, A., Arif, M., Rizwan, A.R., et al.: Mainindex sorting algorithm. In: Soft Computing Applications: Proceedings of the 7th International Workshop Soft Computing Applications (SOFA 2016), vol 17, pp. 253–264. Springer, Berlin (2018)
Allasia, G., Besenghi, R.: Numerical calculation of incomplete gamma functions by the trapezoidal rule. Numerische Mathematik 50(4), 419–428 (1986)
Axtmann, M., Witt, S., Ferizovic, D., et al.: Engineering in-place (shared-memory) sorting algorithms. ACM Trans. Parallel Comput. 9(1), 1–62 (2022)
Bambury, H., Bultel, A., Doerr, B.: An extended jump functions benchmark for the analysis of randomized search heuristics. Algorithmica 1–32 (2022)
Busbridge, I.W.: On the integro-exponential function and the evaluation of some integrals involving it. Q. J. Math. 1(1), 176–184 (1950)
Carlen, E.A., Zhang, H.: Monotonicity versions of Epstein’s concavity theorem and related inequalities. Linear Algebra Appl. 654, 289–310 (2022)
Chen, T., Chen, S., Zhang, K., et al.: A jump point search improved ant colony hybrid optimization algorithm for path planning of mobile robot. Int. J. Adv. Robot. Syst. 19(5), 17298806221127952 (2022)
Chukhrov, I.: Boolean functions minimization problem: conditions of minimality and the probabilistic method. Math. Probl. Cybern. 20, 7–24 (2022)
Darmawantoro, R.Y., Utami, Y.R.W., Kustanto, K.: Implementasi binary search untuk data obat di apotek. Jurnal Teknologi Informasi dan Komunikasi (TIKomSiN) 10(1), 76–84 (2022)
Dutta, A., Chhabra, V., Kumar, P.K.: A unified vista and juxtaposed study on sorting algorithms. Int. J. Comput. Sci. Mob. Comput. (2022)
Dutta, A., Choudhury, M.R., Kundu, K.: Validation of minimal worst-case time complexity by Stirling’s, Ramanujan’s, and Mortici’s approximation. In: 2022 3rd International Conference for Emerging Technology (INCET). IEEE, pp. 1–4 (2022)
Ferrada, H.: A sorting algorithm based on ordered block insertions. J. Comput. Sci. 64(101), 866 (2022)
Gonnet, G.H., Rogers, L.D., Alan George, J.: An algorithmic and complexity analysis of interpolation search. Acta Inform. 13, 39–52 (1980)
Karatsuba, E.A.: On the asymptotic representation of the Euler gamma function by Ramanujan. J. Comput. Appl. Math. 135(2), 225–240 (2001)
Liu, J.P., Tsai, C.M.: Binary computer-generated holograms by simulated-annealing binary search. In: Photonics, MDPI, p. 581 (2022)
Peterson, W.: Open addressing. IBM J. Res. Dev. 1, 130–146 (1957)
Rudolph, M.: Index of Notations, pp. 333–335. Cambridge University Press, Cambridge (2022)
Shneiderman, B.: Jump searching: a fast sequential search technique. Commun. ACM 21(10), 831–834 (1978)
Yang, Z., Li, J., Yang, L., et al.: A smooth jump point search algorithm for mobile robots path planning based on a two-dimensional grid model. J. Robot. (2022)
Ye, J., Xie, L., Wang, H.: A water cycle algorithm based on quadratic interpolation for high-dimensional global optimization problems. Appl. Intell. 53(3), 2825–2849 (2023)