$[$Total $5pts$ Given a one$-$dimensional array $)(2,$ we consider the problem of finding number of pairs $(i,j),$ such that: $A[i]>2^{**}A[j](1,6),(2,5),(2,6),(3,5),(3,6),(3,8),(4,5),(4,6),(4,8),(7,8)(A,1,n)T(n)(A,1,n)T(n)T(k)T(n)k.$ Solve $itto$ determine the upper bound $ofT(n)\mathrm{.}1i,$ and $A[i]>2^{**}A[j].$ Use the following array $asan$ example, the respective solution for this problem should $be10$ and the corresponding pairs are:

$(1,6),(2,5),(2,6),(3,5),(3,6),(3,8),(4,5),(4,6),(4,8),(7,8)$

$\begin{array}{cc}1& 2\\ 3& 4\\ 5& 6\\ 7& 8\\ 4& 5\\ 8& 10\\ 2& 1\\ 7& 3\end{array}$

Question #$1[4pts]$: Let $us$ use Pairs $(A,1,n)to$ represent the solution, apply the divide$-$andconquer technique $to$ design $an$ algorithm which solves the problem. Clearly write your algorithm $in$ pseudo$-$code similar $as$ those inside your textbook and feel free $to$ add additional return values $if$ needed.

Question #$2[1pt]$: Let $T(n)be$ the running time $of$ Pairs $(A,1,n)in$ question #$1.$ Write the recurrence expressing $T(n)in$ terms $ofT(k)$ for some $k.$ Solve $itto$ determine the upper bound $ofT(n).$