Analysis of Algorithms:

Following code segment is the JAVA implementation of Binary Search,

int binarySearch$($int arr$[],$ int l$,$ int r$,$ intx$)$

$\{$

if $(\}$r$>=1$

$\{$

int mid $=$ l $+($r $-1)/2$;

if $($arr$[$mid$]==$ x$)$

return mid;

if $($arr$[$mid$]>$ x$)$

return binarysearch$($arr$,1,$ mid$-1,$ x$)$;

return binarysearch$($arr$,$ mid$+1,$ r$,$ x$)$;

$\}$

return $-1$;

$\}$

The time complexity of all divide$-$and$-$conquer algorithms can be expressed using following

recurrence:

$T(n)=\{\begin{array}{ccc}(1)& if& nc\\ aT(\frac{n}{b})+D(n)+C(n)& \text{o}\text{t}\text{h}\text{e}\text{r}\text{w}\text{i}\text{s}\text{e}& \end{array}$

Binary search is a divide$-$and$-$conquer algorithm, determine the values of constants $a,b,$ and $c,$

and the orders of growth of $C(n)$ and $D(n)$