Below is a linear time complexity algorithm Max-Min-VER1 to find the biggest and smallest element a given list.

Input: A is a given list

Output: two integers

Example: Given A = {1, 5, 9, -3}. It returns -3 (the smallest element), and 9 (the biggest element)

Max-Min-VER1(A, n)

Line 1: large A[0]

Line 2: for I from 1 to n - 1 do //n 1 iterations

Line 3: large Math.max(large, A[I]) // one comparison

Line 4: small A[0]

Line 5: for I from 1 to n - 1 do

Line 6: small Math.min(small, A[I])

Line 7: return large and small

1. Implement this algorithm (java)
2. Answer the question - How many comparisons are used in the algorithm?

Improve the above Max-Min-VER1(A, n) to decrease the number of comparisons. Name your algorithm Max-Min-VER2.

Requirements

1. using the format show in ( to write your pseudocode)

Input: A is a given list

Output: two integers

Example: Given A = {1, 5, 9, -3}. It returns -3 (the smallest element), and 9 (the biggest element)

Max-Min-VER2(A, n)

Line 1:

Line 2:

Line 3:

Line 4:

Line 5:

2. implementation of Max-Min-VER2 (you may use any language, such as Java, C++, C#, python etc)
3. Compare Max-Min-VER1 and Max-Min-VER2 using a table or graph for the time used in milliseconds for running 100 randomly generated lists of each input size 10², 10⁴, and 10⁶.