next up previous

CSE 5311 Fall 1999

Quiz #1

(14 points.) Apply the divide-and-conquer principle discussed in class to searching. To search for a key in a set of n keys, the algorithm divides the set into two subsets of n/2 keys and searches each subset recursively.

Provide pseudocode for the algorithm and perform a line-by-line analysis of the algorithm.
Generate a recurrence relation for the run time and solve it using any of the methods described in class.

(6 points.) Is the following statement true or false? \(f(n) \;+\; g(n) \;=\; \Theta(min(f(n), g(n))).\) Explain your answer.