2. 10 marks) Worst-case and best-case algorithm analysis. Consider the following function, which takes in a list of integers. def myprogram(L: List Lint]) ->None: n len(L) while i0: i = ? // 2 #?nteger dtvsston, rounds down x1 9 else: Let WC(n) and BC(n) be the worst-case and best-case runtime functions of myprogram, respectively where n represents the length of the input list L. You may take the runtime of myprogram on a given list L to be equal to the number of executions of the while loop. (a) 3 marks] Prove that WC(n) E O(n) (b) [2 marks] Prove that WC(n) E ?(n) (c) [2 marks] Prove that BC(n) E O(log n) (d) [3 marks] Prove that BC(n) e ?(log n) Note this is actually the hardest question of this problem set. A correct proof here needs to argue that the variable x cannot be too big, so that the line i x docsn't cause i to decrcase too quickly