Some results on the asymptotic behavior of functions on subsets of the natural numbers
David F. McAllister, Yale N. Patt · 1979
When analyzing the computational complexity of divide and conquer algorithms, the complexity function is usually specified by means of a recurrence relation where the argument is restricted to a subset S of the natural numbers, N. This system is then used to characterize the asymptotic behavior of the algorithm for a corresponding restricted set of inputs. A careful and sometimes complicated argument is then carried out to make assertions about the asymptotic behavior of the algorithm for all inputs (Aho, Hopcroft and Ullman [1974]). In certain cases, the argument can be greatly simplified if the complexity function and the set S have special properties. In this paper, we develop these properties for some important classes of asymptotic behavior.