Question $2$

$($a$)$ Apply the same approach we used in class to solve the recurrence T$($n$)=3$T$($n$/2)+$ O$($n$).$ What is the general form of the k$-$th term in this case? What value of k should be used to find the final answer?

$($b$)$ Solve the recurrence T$($n$)=$ T$($n$1)+$O$(1),$ which is not covered by the master theorem. Can you find a solution for this case?