Write your answers as specified below.
a) Write the key idea for the algorithm design.
b) Write the pseudocode of the algorithm based on the key idea. The pseudocode must be executable to produce correct result.
c) Write the recurrence relation expressing the run time T(n). Use the number of comparisons between data items (i.e., numerical values) as the runtime metric.
d) Solve the recurrence relation to derive T(n)=O(logn). It suffices to derive a closed functional form (i.e., T(n)=logn ); you do not need to prove O(logn ) formally (i.e., using the formal definition of big-O). Show the derivation steps using either the recursion tree of telescoping technique; we can make the simplifying assumption that n is a power of 2 number.
We can consider each of the two databases virtually sorted through queries for finding the k^th smallest data item, so let's denote the k^th smallest data item of each database as A[k] and B[k] where A and B denote the two databases of size n each. Hint: the size of each database considered can be reduced to half at each recursion.