Question

Let A be an array of non-decreasing N integers. Write an algorithm that returns the number of pairs of integers in A that are equal. Analyze your algorithm thoroughly. Your analysis should include a thorough examination of both the best and the worst-case scenarios. This includes a description of what the best and worst cases would look like. You should include both space and time in your analysis, but keep in mind that space refers to “extra space,” meaning in addition to the space already used for the input.

Hint: You can assume there is a (1) function called nChoose2(int n) that calculates the value of C(n, 2).

Answer 1

Solution:

The array is given to us in sorted order and the order is increasing order, which means the smallest to the largest the elements in the array are sorted.

Algorithm:

1. Begin
2. set count to 0, //count= 0
3. for every element in the array
4. for j=0 to array[i]<=array[i]
5. compare it to its right-hand side of elements until our element is smaller than the element present in the right-hand side, //if(array[i]==array[j])
6. if two elements are found equal
7. count++
8. end for
9. end for
10. Display count //This is the number of pairs of integers that are equal
11. End

Analysis:

So the array is already sorted, now there is a for loop in the code which is running n number of times to traverse the complete array considering there is n number of elements in the array. Now another loop is ran through in the algorithm which is running until a greater number is spotted in the array. This loop will be running twice or thrice each time because then the condition will terminate, this will make the overall complexity of the algorithm as cn, where c is some positive constant.

The time complexity will be T(n)= O(n).

Space complexity is O(1), since no extra space is taken.

Hit the thumbs up if you liked the answer. :)