Consider the following recurrence function: T(n)=T(n/2)+1 (i) (3 marks). Solve the recurrence using the master method. Show your work. Master Method (ii) (5 marks). Use induction to show that T(n)=O(n). Answer: (i) Master Method (ii) Induction