Question $2(40$ points$)$

a$)(10$ points$)$

Solve the recurrence

$t(n)=t(\frac{n}{2})+lo{g}_{2}n,$ such that $t(1)=0.$

Assume in your solution that $n$ is a power of $2,$ that is$,n=2^m$ so $m=lo{g}_{2}n.$

b$)(10$ points$)$

Verify that your answer in $($a$)$ is correct using a proof by mathematical induction, namely perform induction on the variable $m.$

c$)(10$ points$)$

If two positive integers $n_1$ and $n_2$ have $N_1$ and $N_2$ decimal digits, respectively, then computing their product $n_1^{?}{n}_2$ using the grade school multiplication algorithm has time complexity $O(N_1{N}_2).$

Question: For a given positive integer $n,$ what is the $)$ time complexity of computing $n^n,$ that is$,n$ to the power $n?$