Recall from Chapter 5 (or see Figure 6.42) an algorithm that merges two sorted arrays into a single sorted array. Give a recurrence relation T(n) describing the running time of merge on two input...

Recall from Chapter 5 (or see Figure 6.42) an algorithm that merges two sorted arrays into a single sorted array. Give a recurrence relation T(n) describing the running time of merge on two input arrays with a total of n elements, and prove that T(n) = Θ(n).