2014/08/11 by Igor Stassiy, Stassiy, Igor
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Computational Complexity (cs.CC) #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.CC #cs.DS #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1408.5422
Master thesis
arxiv created 2014/08/11 · openalex publication_date 2014/08/11 · arxiv updated 2014/08/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this master thesis we analyze the complexity of sorting a set of strings. It was shown that the complexity of sorting strings can be naturally expressed in terms of the prefix trie induced by the set of strings. The model of computation takes into account symbol comparisons and not just comparisons between the strings. The analysis of upper and lower bounds for some classical algorithms such as Quicksort and Mergesort in terms of such a model was shown. Here we extend the analysis to another classical algorithm - Heapsort. We also give analysis for the version of the algorithm that uses Binomial heaps as a heap implementation.