Question

Let T(n) denote the running time for the Sort-and-Count algorithm (below). Sort-and-Count(L) { if list L has one element return 0 and the list L Divide the list into two halves A and B (r1, A) = Sort-and-Count(A) (r2, B) = Sort-and-Count(B) (r3, L) = Merge-and-Count(A, B) r = r1+r2+r3 return r and the sorted list L } Assuming that Merge-And-Count(A,B) runs in time Al+IB| what is the recurrence for T(n)? T(n) = 2T(n/2)+1 T(n)=(n/2) + n T(n) = 2T(n-1) + 1 T(n) = Tỉn/2)+1 - T(n) = 2T(n/2) + n T(n) = 2T(n/2)+log n

Answer 1

Answer:

The answer is "$\bold{T(n) = 2T(\frac{n}{2}) + n}$"

Explanation:

Given:

The Merge-And-Count of (A,B) runs in time |Al+IB|

T(n) recurrence=?

Calculating the value of the recurrence:

$\to T(n) = T(\frac{n}{2}) + T(\frac{n}{2}) + f(|A| + |B|)\\\\ \therefore f(|A| + |B|) = n\\\\ \to T(n) = 2T(\frac{n}{2}) + n$