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

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

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

• implementation in C++
• Answer the question - How many comparisons are used in the algorithm?

improve above algorithm to decrease the number of comparisons

and Compare both for the time used in milliseconds for running 100 randomly generated lists of each input size 10², 10⁴, and 10⁶.