math - Determining recurrence relation from recursive algorithm -

i got following recursive algorithm , asked find recurrence relation.

int search(int a[], int key, int min, int max) {     if (max < min)      // base case        return key_not_found;     else     {        int mid = midpoint(min, max);         if (a[mid] > key)               return search(a, key, min, mid-1);        else if (a[mid] < key)           return search(a, key, mid+1, max);        else           return mid;       // key found     } } 

the solution t(n) = t(n/2) + 1 not sure why t(n/2) ? , why + 1? + 1 because recursion takes constant time? or what? understand solution?

your code implementation of binary search. in binary search, @ each recursive call break sorted array half, search element in left part of array if element smaller middle element, or search right part of array if element bigger middle element or stop if looking middle element.

now if n shows number of elements in sorted array, whenever break 2 same size arrays, problem size decreases n/2, , since call search function once either way on n/2 array, can :

t(n) = t(n/2)+o(1)

the o(1) addition because of if run check in condition are.