Question $3[2$ marks$]$

$($a$)[1$ mark$]$ Use the substitution method to show that a solution of $T(n)=T(\frac{n}{2})+1$ is

$O(n).$

$($b$)[1$ mark$]$ Use recursion tree to show that $O(n)$ is not a tight solution for $T(n)=T(\frac{n}{2})+1$

recurrence.