code can be written in python, java, C, or C++

1. (2.5+2.5+2.5+2.5 marks) Write two algorithms to find both the smallest and largest numbers in a list of in numbers. In first algorithm (i.e., Algo. 1), you simply write one loop to find the minimum and maximum. So there will be 2(n - 1) comparisons. In second algorithm (i.e., Algo. 2), you try to find a method that does at most 1.5n comparisons of array items. (Hints: You can reduce the number of comparisons by comparing pairs of numbers; that is find max(a,b) and min(a,b) in one comparison. Then you need only 2 more comparisons to update the overall min and max, for a total of 3 comparisons for each pair of numbers. The total number of comparisons would be 3n/2 = 1.5n.) Implement both algorithms (i.e., Algo. 1 and Algo. 2). Determine the largest list size (i.e., n) that Algo. 1 can process and still compute the answer within 60 seconds. Report how long it takes Algo. 2 to compute this answer. You can randomly populate the list. 1 2. (5 marks) Is 8n6 + 7 +6n +57 +4n2 + 3n+2 (n)? Prove? 3. (5 marks) is no (8n +7 +6n* + 5m +4n2 + 3n+2)? Prove? 4. (5 marks) Using the definitions of O and 2 show that 13n? + 140 + 1500 + 16n + 1773 + 18n" +19n + 20 O(n) 5. (15 marks) Solve the following recurrence relations and give a bound for each of them (you do not need to show/prove how the bound is obtained): (a) T(n) = T(n-1) + 2n (assume T(0) = 0) (b) T(n) = 2T(n-1)+c (assume T(0) = 0) (c) T(n) = 2T (n/3) +7 (assume T(1) = 1)