6. (10%) Briefly describe "binary search" and "searching on a binary search tree", and make a comparison between them in terms of data structure constraints and time complexity.

(5%) (b) The Knuch-Morris-Pratt (KMP) algorithm is a string matching algorithm designed to reduce redundant symbol comparisons in string matching. What is the big-O time complexity, in terms of NP and Ns, of the KMP algorithm?