""" QUESTION 4: Analysis

3 marks, ~10 minutes

(a) Consider the following recursive function where the return value of the base case is hidden intentionally (so that you can't get the answer by simply running the code).

def mystery(n: int) -> int:

if n <= 1: return # RETURN VALUE HIDDEN # if n % 3 == 0: return mystery(n-1) + 1 return 2 * mystery(n-1) - mystery(n-2) + 1

All we know now is that mystery(5) returns 14.

What are the return values of mystery(6) and mystery(8)? Write your answers below. If there is not enough information to determine the return value, write "unknown" as the answer.

TODO: Write your answers below.

mystery(6) returns ____ [1 mark]

mystery(8) returns ____ [1 mark]

(b) Consider inserting a sequence of 7 values, in the following order, into an initially empty binary search tree. One of the values is hidden.

43, 21, 32, __hidden__, 42, 40, 35

We know that the hidden value is an integer that is _different_ from all other values in the sequence, and we know that the resulting BST has a height of 7, i.e., the maximum possible height with 7 nodes.

Below, write down ALL possible values of the hidden value. If no possible value exists, write "impossible" as the answer. If infinitely many values are possible, write "infinite" as the answer.

TODO: Write your answer below [1 mark]

"""