I need help with the following question and I would appreciate it if clear explanations are given so that I understand the solution. \

Thanks in advanced.

Q4: The following Function performs binary search for x on a given array arr. //arr is array, l is left index, r is right index, x is element to find int binarySearch (int arr[], int l, int r, int x) if (r >= 1) { int mid = l + (r - 1) / 2; // If the element is present at the middle by itself if (arr(mid] == x) return mid; // If element is smaller than mid, then // it can only be present in left subarray if (arr(mid] > x) return binarySearch (arr, l, mid - 1, x); // Else the element can only be present in right subarray return binarySearch (arr, mid + l, r, x); // We reach here when element is not present in array return -1; Q4 Part A: Write a recurrence relation representing the binary search algorithm in terms of n (size of array). T(n) = Q4 Part B: Solve the recurrence relation. Show your work. Give both, the exact answer and the general O case. (so using the master theorem won't cut it since that won't give you the exact recurrence relation solution)