need help

Consider the following recursive function for n0. For the sake of simplicity you can assume n is power of 2 or n=0. \begin{tabular}{l} \hline Algorithm 1 int recFunc(int n ) \\ \hline// Base Case: \\ if n=1 then \\ return 1 ; \\ end if \\ //Recursive Case: \\ int a=0 \\ int j=recFunc(n/2) \\ while j>0 do \\ a=a+2 \\ j=j1 \\ end while \\ return a \end{tabular} (1) (2 points) Use strong induction to proverecFunc(n) returns a value n. (2) (2 points) Set up a runtime recurrence for the runtime T(n) of this algorithm. Hint: Use the fact that recFunc(n)n to help in setting up the recurrence. (3) (1 point) Solve this runtime recurrence using the master theorem or if the master theorem cannot be applied, state the reason and give an upper bound (big-Oh) which is as tight as you can justify