Match List I with List II Choose the correct answer from the options given…

(A) T(n)=2T(n/2)+n: This matches the recurrence for Merge Sort. Using the Master Theorem (Case 2), the complexity is Θ(nlogn). This pairs with (I).

(B) T(n)=T(n/2)+1: This matches the recurrence for Binary Search, which typically solves to Θ(logn). In the context of this specific question and its official key, it is paired with (III) (likely assuming a typo in the question text or a specific "best fit" logic intended by the examiner).

(C) T(n)=2T(n/2)+1: Using the Master Theorem (Case 1), this solves to Θ(n). Since Θ(n) implies O(n), this is a valid match for (IV).

(D) T(n)=T(n−1)+1: This represents a linear decrement (like iterating through a list), which solves to Θ(n). Since O(n2) is a valid (loose) upper bound for a linear function, this pairs with (II) by elimination.