(b) For an integer n, with n > 0, 7(n) is defined by the recurrence system in part (a) above, and F(n) is defined by the formula F (n) = 7 x n + 4. Prove by mathematical induction that I(n) = F(n) (for all integers n with n > 0). Give a classification of T(n) as (f(n)) for a suitable function f in the hierarchy of functions given on page 21 of the M263 Course Handbook. [12] a (c) Recall (Unit 14, page 6) that a full binary tree of depth n has 2" I nodes. Suppose that t is a full binary tree, and let i be the number of nodes in t. If the application of recInBST were to be restricted to input trees which are full, then it might be appropriate to regard the size of the input' as the number of nodes, i, rather than as the depth of the tree, n. Give a formula Uli) relating the number of statement executions for recInBST (in the worst case) to i, the number of nodes in the full binary tree t. With the size of the input measured in this way, what is the order of the time efficiency function Ui)? (Give a classification of U(i) as (fi)) for a suitable function f in the hierarchy of functions given on page 21 of the M263 Course Handbook.) [8] a (b) For an integer n, with n > 0, 7(n) is defined by the recurrence system in part (a) above, and F(n) is defined by the formula F (n) = 7 x n + 4. Prove by mathematical induction that I(n) = F(n) (for all integers n with n > 0). Give a classification of T(n) as (f(n)) for a suitable function f in the hierarchy of functions given on page 21 of the M263 Course Handbook. [12] a (c) Recall (Unit 14, page 6) that a full binary tree of depth n has 2" I nodes. Suppose that t is a full binary tree, and let i be the number of nodes in t. If the application of recInBST were to be restricted to input trees which are full, then it might be appropriate to regard the size of the input' as the number of nodes, i, rather than as the depth of the tree, n. Give a formula Uli) relating the number of statement executions for recInBST (in the worst case) to i, the number of nodes in the full binary tree t. With the size of the input measured in this way, what is the order of the time efficiency function Ui)? (Give a classification of U(i) as (fi)) for a suitable function f in the hierarchy of functions given on page 21 of the M263 Course Handbook.) [8] a A specification of a function INBST, and implementation recInBST, are given below. a function INBST(t in Bin Tree of Int, val in Int) return in Bool pre t is a binary search tree. post The returned value is true if the integer val appears at a node of the tree t, and is false if val does not appear in t. (If t is empty, then false is returned.) function INBST (t,val) { // recInBST var b in Bool // (1) if (t.isEmpty()) then 17 (2) { b <-- false } // (3) else if(val t.getRoot()) then // (4) b <-- true 77 (5) if (val t.getRoot ()) then // (8) b <-- INBST (t.rightTree (), val) // (9) ] } return b // (10)