$[6$ pts$,3$ per part$]$: Solve the following two recurrences using the Master Method. Show your

work. If either uses case $3,$ show that the regularity condition holds.

a$.T(n)=2T(\frac{n}{4})+n^{0\mathrm{.}5}lgn$

Solution:

b$.T(n)=T(\frac{n}{4})+n^2$

Solution:

$[4$ pts$]$ Suppose you have an array of jnts that is sorted from least to greatest but where the

least element is not necessarily at index $0$ of the array. Think of circular array from ICS $240.$

For instance:

$7,8,11,14,1,2,3,5$

Propose a divide and conquer algorithm to efficiently find the index of the largest element of the

array. Explain it carefully. Analyze the running time of your algorithm $($informally$).$ For simplicity,

you may assume that the size of the array is an exact power of $2.$