1. In class, we gave an algorithm for finding the maximum segment sum in a list. That algorithm simply returned the maximum segment sum and nothing else. When working to improve the runtime of a recursive algorithm, it often helps to return more information from recurv calls. Here's some new Python code for us to consider for this problem. 1 # helper returns a tuple with the following information: 2 # 0- aximum segment sum 3 # 1 naximum segment sum starting at A[low] 4 # 2 - maximum segment sum ending at A[high] 6 def helper (A, low, high): 79 Pre: ??? 8 Post ??? 10 if low-high : best max (A [low], 0) return best, best, best 12 13 mid(lo high) // 2 14 1-max-sum, 1-start, 1-end = helper(A, low, mid) 15 r-max-sum, r-start, r-end = helper (A, mid+1, high ) 16 start= 1-start 17 endr.end 18 max-sun. ax (1, max-sum, r_max-sum, 1-end + r-start) 19 return ax sum, start, end 20 21 def max segment sum (A): 22 Pre: A is a nonempty list of nuabers 23 Post: Returns maximum seg ent sum of A 24 25 return helper (A, len(A) 1)0] (a) [1 What is the asymptotic worst-case runtime for this algorithm Justify your answer (b) [5] Does this algorithm work correctly? If yes, prove its correctness. If not, please carefully explain the problem, fix the problem by supplying updated Python code, and then prove correctness of your new oode. Include preconditions and postconditions for helper. (If you decide to update the code, be sure not to change its Theta bound.)