Which is the best approximation of the summation 1 + 1/2 + 1/3 + ... + 1/n obtained during our analysis of the average case of Quick Sort (and BST)?

A)

(log log n)

B)

(log n)

C)

(n)

D)

(n log n)

E)

(1/n!)

F)

(n!)

******************

Techniques for Recurrence-Solving

Which recurrence-solving technique is utilized in setting R(n) = T(n) / (n+1) during our average-case analysis of Quick Sort?

A)

Telescoping

B)

Domain Transformation

C)

Range Transformation

D)

Integration

E)

Expansion

F)

Amortization

************

Consider a BST containing 65536 words, of which 85 begin with the character sequence EX. The BST's alphabet is limited to the 26 upper-case letters A-Z, and the longest word in the BST is 42 letters. What is the worst case of the number of key-comparisons to search for the word EXAMINATION?

A)

11

B)

16

C)

26

D)

42

E)

85

F)

65536