Question

Write two algorithms to find both the smallest and largest numbers in a list of n numbers.

In first algorithm, you simply write one loop to find the minimum and maximum. So there will be 2(n - 1) comparisons.

In second algorithm, you try to find a method that does at most 1.5n comparisons of array items.

Determine the largest list size (i.e., n) that Algorithm 1 can process and still compute the answer within 60 seconds. Report how long it takes Algorithm 2 to compute this answer.

Answer 1

Algorithm 1:

max = A[0], min = A[0]
for each i in A
    if A[i]>max then max = A[i]
    if A[i]<min then min = A[i]

Algorithm 2:

if (a[0] > a[1]) {

    curr_max = A[0]

    curr_min = A[1]

  } else {

    curr_max = A[1]

    curr_min = A[0]

  }

  for (i = 2 to n-2) {

    if (A[i] > A[i + 1]) {

      min = min(curr_min, A[i + 1])

      max = max(curr_max, A[i])

    } else {

      min = min(curr_min, A[i])

      max = max(curr_max, A[i + 1])

    }

    i = i + 2

  }

  if (n % 2 == 1) {

    min = min(curr_min, A[n-1])

    max = max(curr_max, A[n - 1])

  }

2*(n-1) = 60 => n = 31

Hence, the largest list size that Algorithm 1 can process and still compute the answer within 60 seconds = 31.

Now, time taken by algorithm 2 = 1.5 * 31 = 46.5