Formally analyze the runtime of the divide and conquer algorithm, giving a recurrence relation and a big oh bound on the runtime of the algorithm.

/ A recursive divideConquer search function. It returns i where A[i]==i // otherwise NULL int divideConqueri(int arr[], int l, int r) { if (r >= l) { int mid = l + (r - l) / 2; // If the element is present at the middle // itself if (arr[mid] == mid) return mid; // If element is smaller than mid, then // it can only be present in left subarray if (arr[mid] > mid) return divideConqueri(arr, l, mid - 1); // Else the element can only be present // in right subarray return divideConqueri(arr, mid + 1, r); } // We reach here when element is not // present in array return NULL; }