QUESTION 3 Consider the following recurrence relations: T(n) = T(n/2) + 0(1) T(n) = T(n-l ) + 0( 1 ) T(n) 2T(n/2)+ O(1) T(n)- T(n-1)+ O(n) T(n) 2T(n/2) O(n) For each of the above recurrences, the base case is T(1) O(1). Match these recurrence relations to their appropriate closed form, expressed in Big-O notation. ' T(n) = T(n/2) + 0(1) T(n) = T(n-l ) + 0( 1 ) ' T(n) = 2T(n/2) + 0(1) T(n) = T(n-1 ) + O(n) T(n) = 2T(n/2) + 0(n) A. O(nlogzn) B. Olog2n) C.O(n) D.O(n2)