Multiple-size divide-and-conquer recurrences
Ming‐Yang Kao · ACM SIGACT News · 1997
This note reports a tight asymptotic solution to the following recurrence on all positive integers n:where• k is a positive integer,Since no _> max,= 1 1---~,1 Fbi.nl _ no.Thus, the T(n) term on the left-hand side of (1) is defined on T-terms with smaller n, and (2) properly specifies the initial values of T.A special case of this recurrence, namely, k = 1, is discussed in [2, 5] and standard textbooks on algorithms and is used extensively to analyze divide-and-conquer strategies [1,4].A specific recurrence with k -2 is used to analyze a divide-and-conquer algorithm for selecting a key with a given rank [1,3,4].