Given a sorted array of distinct integers $A[1,$dots,$n],$ you want to find out whether there is an

index i for which $A[i]=i.$ Give a divide$-$and$-$conquer algorithm that runs in time $O(nlogn).($a$)$ Solve the following recurrence relation and give an asymptotic bound for it:

$T(n)={\displaystyle \underset{i=1}{\overset{n-1}{}}}T(i)$

$($b$)$ Use a recursion tree to compute an asymptotic solution for the recurrence

$J(n)=J(\frac{n}{2})+J(\frac{n}{3})+n.$