Description
Show the steps of deriving your answers. Points will be deducted for answers without adequate steps discussed or not compliant with the specification. Submit your homework via Blackboard as one PDF or Word document. Refer to the grading guidelines posted on Blackboard to understand how the submitted exercises will be graded.
-
(25) [Recurrence relation] Given the following recurrence equation of T(n), express T(n) in an asymptotic big-O function from. Use the telescoping approach. State any simplifying assumption you are making. It suffices to derive the functional form only; there is no need to
prove it by the formal definition of big-O.
( ) = { (2) + 2 for ≥ 2
-
-
for = 1
-
-
(25) [Divide and conquer: median of two data sets.] Textbook Exercise 1 in Chapter 5. Write the algorithm with a narrative explanation, and write the recurrence relation expressing the run time T(n) and solve the recurrence relation to derive O(log n). Pseudocode is okay for the algorithm, but it must be executable precisely. Use the number of comparisons between data items (i.e., numerical values) as the runtime metric. To solve the recurrence relation, it suffices to derive a closed functional form (i.e., O(log n)) (show the derivation steps, using either telescoping or recursion tree); there is no need to prove O(log n) formally. We can consider each of the two databases virtually sorted through queries for finding the kth smallest data item, so let’s denote the kth 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.
