# part a analyze the following recurrences and show their time complexity functions us 5153058

Part A Analyze the following recurrences and show their time complexity functions using (I) iteration method and (2) Master Theorem. AI. T(n) = 2T 3 A2. T(n) = 3T 2n АЗ. Т(п) — Т(п — 2) + 3 А4. Т(п) — 2Т (п — 1) + 1 A5. T(n)= 4T +n log n A6. T(n) = 3T +n log n n2 A7. T(n) = 27 Part B Do 2.3-4 (р39) and Problem 2-1 (р39) Part C Implement MERGE-SORT() algorithm that reads from a file named “inputHW02.txt” a list of double numbers (max = 3,000,000 numbers), sorts those numbers and indicates time consumption. This programming question will address the advantage of using iteration loops over recursive calls as well as using INSERTION-SORT() as a procedure in MERGE- SORT() Your program must perform the following actions: Opens the given file name and reads all double numbers. For simplicity, we assume this file only contains numbers and nothing else. mplements the function INSERTION-SORT() that only sort an array of maximum 25 numbers. The idea is that INSERTION-SORT() will be used as a sub-procedure to sort any sub-array when its size is small enough Four versions of MERGE-SORT() namely I. 2. 3. MERGE-SORT-A(): Using recursive calls and NO INSERTION-SORT() as a sub-procedure MERGE-SORT-B(): Using ITERATIVE loops (i.e, NO recursion) and NO INSERTION-SORT() a. as a sub- procedure. MERGE-SORT-C(): Using recursive calls and INSERTION-SORT() as a sub-procedure d. MERGE-SORT-D(): Using ITERATIVE loops (i.e, NO recursion) and INSERTION-SORT() c. as a sub