2. 10 marks] Worst-case and best-case algorithm analysis. Consider the following funetion, which takes in a list of integers. 1 def myprogram(L: List[int])None: 2 nlen (L) i=n-1 5While i >0: if L[1] % 2-0: i i // 2 # 1nteger division, rounds doun x+= 1 else: 1O 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). (c2 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 decrease too quickly