586 CHAPTER 9 Recurrence Relations
- For the two versions of the sorting routine called INSORT, determine the complexity
of the code presented:
(a) function INSORT [X, n]
if n < 1 then
return
INSORT[X, n - 1]
T = X[n]
for i = n - 1 down to I
if X[i] < T then
X[i ± 1] = X[i]
X[i] = T
T = X[i](b) function INSORT[X, n]
if n < 1 then
return
for j = 2 to nT = X[j]
for i = j - 1 down to 1
X[i] > T then
X[i + 1] = X[i]
X[i] = T
T = X[i]- (a) Find a recurrence relation for the number of binary decision trees on a set of n
distinct numbers. (Hint: See Figure 6.42).
(b) Use the recurrence relation found in part (a) to determine the number of binary
search trees for 5, 7, 9, and 10 items.