2. [10 marks] Worst-case and best-case algorithm analysis. Consider the following function, which takes in a...

  

Transcribed Image Text:

2. [10 marks] Worst-case and best-case algorithm analysis. Consider the following function, which takes in a list of integers. 1 3 4 5 6 7 8 9 10 def myprogram (L: List [int]) -> None: n = len (L) i = n - 1 x = 1 while i > 0: if L[i] % 2 == 0: i = 1 // 2 x += 1 else: #integer division, rounds down i = x 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) = O(n). 2. [10 marks] Worst-case and best-case algorithm analysis. Consider the following function, which takes in a list of integers. 1 3 4 5 6 7 8 9 10 def myprogram (L: List [int]) -> None: n = len (L) i = n - 1 x = 1 while i > 0: if L[i] % 2 == 0: i = 1 // 2 x += 1 else: #integer division, rounds down i = x 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) = O(n).