Uma Nova Proposta para a Obtenção da Complexidade de Pior Caso do ShellSort

ABSTRACT The worst-case time-complexity of the ShellSort, a comparison sorting algorithm, depends on a sequence of steps given as input. Each step consists of an integer representing an index offset of the pairs of elements that should be compared during the sorting of an input array. Such a complexity is known only to some specific sequences. In this work, we use a relation between the ShellSort and Frobenius number to present a new algorithm that provides an upper bound on the number of comparisons that ShellSort performs, for any given array and sequence of steps. We apply this algorithm, together with an empirical complexity analysis, to study sequences whose worst-case complexities are known through analytical method. We show that the empirical approach succeeded in determining such complexities. Based on such positive results, we extend the study to sequences for which the worst-case complexities are unknown.