Given an algorithm that determines if there is a pair of duplicate entries in th

Question

Given an algorithm that determines if there is a pair of duplicate entries in the sequence.

Input: a1, a2,...,an
          n, the length of the sequence.
Output: "Yes" if there is a duplicate pair and "No" if the elements in the sequence are distinct.

For i = 1 to n - 1
      For j = i+1 to n
            If ( ai = aj ), Return("Yes")
      End-for
End-for

Return( "No" )

Which description corresponds to the type of input that will cause the inner loop of FindDuplicate to execute the most number of times?

Explanation / Answer

As we can see, we select an element which we want to check if its duplicate exists. The element is selected by the outer for loop. SO, the element ai is the element which is to be checked if its duplicate exists or not.

Then we check inside the the inner for loop if any same element exists in the subarray after the i th element.

So, the inner for loop will execute the maximum no of times if the duplicate elements are present in the two extreme points. So, if the duplicate elements are present at index 1 and n, the loop executes (n - 1) number of times which is the maximum.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.