CPS 450 - Homework 4 Due: in class, at class time, Thursday, 2 March, 2023 (1) (15 pts) Suppose we are given array L of sorted lists of integers L[1],,L[k]; for convenience, I will use Li to refer to L[i]. Further, assume that n is a multiple of k,k is a power of 2 , and that each list has kn integers so that the total size of the lists is n. In this problem, we are interested in merging all the k sorted lists to produce one sorted list. By "C = Merge (A, B)", I mean sorted lists A and B are merged to produce the sorted list C as studied in the class. Note that the lists need not be distinct. Assume that lists are implemented in such a way that any addition (deletion) to (from) front/back of the list can be done in constant time. Below are algorithms for the problem. Analyze each algorithm to find an expression for the complexity of the algorithm; provide details. Give a theta bound for the complexity, but you do not have to prove the bound. The complexity will clearly depend on n and k. (a) L=emptylist;fori=1tokL=Merge(L,Li); / List L is the sorted list of all the items */ (b) Consider the following approach using divide and conquer: if there is only one list to deal with, return that as answer. Otherwise, recursively (using the same algorithm) merge lists L1,,L2k to get list Left. Then, recursively merge lists L2k+1,,Lk to get list Right. Merge Left with Right and return the result. Analyze the algorithm to determine its complexity. Justify your answers. Hint: Use the recursion tree to model the complexity/working of the algorithm and find the total cost of each level. (2) (5 pts) Consider the divide and conquer approach from (1b). Suppose the lists L1,,Lk may not all be of the same length but the sum of the lengths of all the k lists is n. You may assume k is a power of 2 . Analyze the complexity of the algorithm in this situation