I need help with these questions.

4. Let T(n) be defined by the recurrence formula: 4 n, and hence T(n) 0(n2). (Hint: follow Example 3 on page 3 of the show that Vr12 1: T(n) induction handout.) 5. Let T(n) be defined by the recurrence formula: 7(n)-19T(In/3]) + 1 n 1, 2 3 n Show that 12 1: T(n) 3n2-1, and hence T(n) = O(n2). (Hint: emulate Example 4 on page 4 of the induction handout. I. Base: check the two cases n = 1, and n = 2 . II. Induction step: show for all n 2 3, that if for any k in the range 1 k