2. [10 marks] Worst-case and best-case algorithm analysis. Consider the following function, which takes in a list of integers. E N co one def myprogram (L: List[int]) -> None: n = len (L) i = n - 1 x = 1 while i > 0: if L[i] % 2 == 0: i = i // 2 # integer division, rounds down x += 1 else: i -= x o o o 6 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(n). (c) [2 marks] Prove that BC (n) E O(log n). (d) [3 marks] Prove that BC (n) E N(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 doesn't cause i to decrease too quickly