1 Introduction
This note reports a tight asymptotic solution to the following recurrence on all positive integers :
for ,  (1)  
for ,  (2) 
where

,

is a positive integer,

and for ,

.
Since , for all and . Thus, the term on the lefthand side of (1) is defined on terms with smaller , and (2) properly specifies the initial values of .
A special case of this recurrence, namely, , is discussed in [2, 5] and standard textbooks on algorithms and is used extensively to analyze divideandconquer strategies [1, 4]. A specific recurrence with is used to analyze a divideandconquer algorithm for selecting a key with a given rank [1, 3, 4].
Let . The characteristic equation of the general recurrence is the equation . Our solution to the general recurrence is summarized in the following theorem.
Theorem 1
If is the solution to the characteristic equation of the general recurrence, then
The key ingredient of our proof for this theorem is the notion of a characteristic equation. With this new notion, our proof is essentially the same as that of the case with [1, 2, 4, 5]. This note concentrates on elaborating the characteristic equation’s role in our proof by detailing an upper bound proof for a certain case. Once this example is understood, it is straightforward to reconstruct a general proof for Theorem 1. Consequently, we omit the general proof for the sake of brevity and clarity.
2 An Example
This section discusses the general recurrence with . To further focus our attention on the characteristic equation’s role, we assume that , is a positive integer, and . Then, according to Theorem 1, . We will only prove . The lower bound proof is similar.
Let . It suffices to show that there exist some positive constants such that . These constants and some others are chosen as follows. Without loss of generality, we assume .
Note that since for all , is a decreasing function. Then since and , and . Thus, the above constants are all positive. We next consider the following new recurrence:
for ,  
for , 
It can be shown by induction that for all . Thus, to prove , it suffices to show for all .
Base Case: for all . This follows from the choice of .
Given some , we need to show .
Induction Hypothesis: for all integers where .
Induction Step:
(4)  
(5)  
(6) 
In this above derivation,
To finish the induction step, note that the righthand side of (6) is at most as desired for the following reasons.

By the choice of ,

Since ,
Acknowledgments
The author found the result in this note in 1986 while teaching a course on algorithms. Since then, he has been teaching it in his classes. He wishes to thank Don Rose for helpful discussions.
References
 [1] A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Computer Algorithms. AddisonWesley, Reading, MA, 1974.
 [2] J. L. Bentley, D. Haken, and J. B. Saxe. A general method for solving divideandconquer recurrences. SIGACT News, 12(3):36–44, 1980.
 [3] M. Blum, R. W. Floyd, V. Pratt, R. L. Rivest, and R. E. Tarjan. Time bounds for selection. Journal of Computer and System Sciences, 7(4):448–461, 1973.
 [4] T. H. Cormen, C. L. Leiserson, and R. L. Rivest. Introduction to Algorithms. MIT Press, Cambridge, MA, 1991.
 [5] G. S. Lueker. Some techniques for solving recurrences. ACM Computing Surveys, 12(4):419–436, 1980.
Comments
There are no comments yet.