Abstract
The fragile complexity of a comparison-based algorithm is f(n) if each input element participates in O(f(n)) comparisons. In this paper, we explore the fragile complexity of algorithms adaptive to various restrictions on the input, i.e., algorithms with a fragile complexity parameterized by a quantity other than the input size n. We show that searching for the predecessor in a sorted array has fragile complexity \(\varTheta (\log k)\), where k is the rank of the query element, both in a randomized and a deterministic setting. For predecessor searches, we also show how to optimally reduce the amortized fragile complexity of the elements in the array. We also prove the following results: Selecting the kth smallest element has expected fragile complexity \(O(\log \log k)\) for the element selected. Deterministically finding the minimum element has fragile complexity \(\varTheta (\log (\mathrm {Inv}))\) and \(\varTheta (\log (\mathrm {Runs}))\), where \(\mathrm {Inv}\) is the number of inversions in a sequence and \(\mathrm {Runs}\) is the number of increasing runs in a sequence. Deterministically finding the median has fragile complexity \(O(\log (\mathrm {Runs}) + \log \log n)\) and \(\varTheta (\log (\mathrm {Inv}))\). Deterministic sorting has fragile complexity \(\varTheta (\log (\mathrm {Inv}))\) but it has fragile complexity \(\varTheta (\log n)\) regardless of the number of runs.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
For simplicity of exposition, we assume the rank is close to one, but the result clearly holds for rank distance to other positions in A.
- 2.
The measure \(\mathrm {Inv}\) is defined as the total number of inversions in the input, where each of the \({n\atopwithdelims ()2}\) pairs of elements constitute an inversion if the elements of the pair appear in the wrong order. The measure \(\mathrm {Runs}\) is defined as the number of runs in the input, where a run is a maximal consecutive ascending subsequence.
References
Afshani, P., et al.: Fragile complexity of comparison-based algorithms. In: Bender, M.A., Svensson, O., Herman, G. (eds.) 27th Annual European Symposium on Algorithms, ESA 2019, 9–11 September 2019, Munich/Garching, Germany. LIPIcs, vol. 144, pp. 2:1–2:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
Ajtai, M., Komlós, J., Szemerédi, E.: An \(O(n \log n)\) sorting network. In: Proceedings of the 15th Symposium on Theory of Computation, STOC 1983, pp. 1–9. ACM (1983)
Ajtai, M., Komlós, J., Szemerédi, E.: Sorting in \(c \log n\) parallel steps. Combinatorica 3(1), 1–19 (1983)
Alekseev, V.E.: Sorting algorithms with minimum memory. Kibernetika 5(5), 99–103 (1969)
Batcher, K.E.: Sorting networks and their applications. In: Proceedings of AFIPS Spring Joint Computer Conference, pp. 307–314 (1968)
Bose, P., Cano, P., Fagerberg, R., Iacono, J., Jacob, R., Langerman, S.: Fragile complexity of adaptive algorithms (2021). To appear in arXiv
Brodal, G.S., Pinotti, M.C.: Comparator networks for binary heap construction. In: Arnborg, S., Ivansson, L. (eds.) SWAT 1998. LNCS, vol. 1432, pp. 158–168. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0054364
Bulánek, J., Koucký, M., Saks, M.E.: Tight lower bounds for the online labeling problem. SIAM J. Comput. 44(6), 1765–1797 (2015)
Chvátal, V.: Lecture notes on the new AKS sorting network. Technical report DCS-TR-294, Department of Computer Science, Rutgers University, New Brunswick, NJ, October 1992
Dowd, M., Perl, Y., Rudolph, L., Saks, M.: The periodic balanced sorting network. J. ACM 36(4), 738–757 (1989)
Estivill-Castro, V., Wood, D.: A survey of adaptive sorting algorithms. ACM Comput. Surv. 24(4), 441–476 (1992)
Fredman, M.L.: Two applications of a probabilistic search technique: sorting x + y and building balanced search trees. In: Rounds, W.C., Martin, N., Carlyle, J.W., Harrison, M.A. (eds.) Proceedings of the 7th Annual ACM Symposium on Theory of Computing, Albuquerque, New Mexico, USA, 5–7 May 1975, pp. 240–244. ACM (1975)
Goodrich, M.T.: Zig-zag sort: a simple deterministic data-oblivious sorting algorithm running in \(O(n \log n)\) time. In: Shmoys, D.B. (ed.) STOC 2014, pp. 684–693. ACM (2014)
Guibas, L.J., Sedgewick, R.: A dichromatic framework for balanced trees. In: 19th Annual Symposium on Foundations of Computer Science, Ann Arbor, Michigan, USA, 16–18 October 1978, pp. 8–21. IEEE Computer Society (1978)
Itai, A., Konheim, A.G., Rodeh, M.: A sparse table implementation of priority queues. In: Even, S., Kariv, O. (eds.) ICALP 1981. LNCS, vol. 115, pp. 417–431. Springer, Heidelberg (1981). https://doi.org/10.1007/3-540-10843-2_34
Jimbo, S., Maruoka, A.: A method of constructing selection networks with \({O}(\log n)\) depth. SIAM J. Comput. 25(4), 709–739 (1996)
Parberry, I.: The pairwise sorting network. Parallel Process. Lett. 2(2–3), 205–211 (1992)
Parker, B., Parberry, I.: Constructing sorting networks from \(k\)-sorters. Inf. Process. Lett. 33(3), 157–162 (1989)
Paterson, M.S.: Improved sorting networks with \({O}(\log {N})\) depth. Algorithmica 5(1), 75–92 (1990)
Pippenger, N.: Selection networks. SIAM J. Comput. 20(5), 878–887 (1991)
Pratt, V.R.: Shellsort and Sorting Networks. Outstanding Dissertations in the Computer Sciences, Garland Publishing, New York (1972)
Seiferas, J.I.: Sorting networks of logarithmic depth, further simplified. Algorithmica 53(3), 374–384 (2009)
Hoory, S., Linial, N., Wigderson, A.: Expander graphs and their applications. BAMS Bull. Am. Math. Soc. 43, 439–561 (2006)
Vadhan, S.P.: Pseudorandomness. Found. Trends Theoret. Comput. Sci. 7(1–3), 1–336 (2012)
Willard, D.E.: Good worst-case algorithms for inserting and deleting records in dense sequential files. In: Zaniolo, C. (ed.) Proceedings of the 1986 ACM SIGMOD International Conference on Management of Data, Washington, DC, USA, 28–30 May 1986, pp. 251–260. ACM Press (1986)
Willard, D.E.: A density control algorithm for doing insertions and deletions in a sequentially ordered file in good worst-case time. Inf. Comput. 97(2), 150–204 (1992)
Yao, A., Yao, F.F.: Lower bounds on merging networks. J. ACM 23(3), 566–571 (1976)
Acknowledgements
This material is based upon work performed while attending AlgoPARC Workshop on Parallel Algorithms and Data Structures at the University of Hawaii at Manoa, in part supported by the National Science Foundation under Grant No. CCF-1930579. We thank Timothy Chan and Qizheng He for their ideas improving the randomized selection algorithm.
P.B was partially supported by NSERC. P.C and J.I. were supported by F.R.S.-FNRS under Grant no MISU F 6001 1. R.F. was partially supported by the Independent Research Fund Denmark, Natural Sciences, grant DFF-7014-00041. J.I. was supported by NSF grant CCF-1533564. S.L. is Directeur de Recherches du F.R.S.-FNRS.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Bose, P., Cano, P., Fagerberg, R., Iacono, J., Jacob, R., Langerman, S. (2021). Fragile Complexity of Adaptive Algorithms. In: Calamoneri, T., Corò, F. (eds) Algorithms and Complexity. CIAC 2021. Lecture Notes in Computer Science(), vol 12701. Springer, Cham. https://doi.org/10.1007/978-3-030-75242-2_10
Download citation
DOI: https://doi.org/10.1007/978-3-030-75242-2_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-75241-5
Online ISBN: 978-3-030-75242-2
eBook Packages: Computer ScienceComputer Science (R0)