Question

Assume you have a sorting algorithm that you can use as a black box. Use the sorting algorithm to sort the input list. Now write an algorithm to count the number of duplicates again. Analyze the time complexity of your algorithm in the worst-case (ignore the time complexity of sorting). Could you improve the worst-case time complexity of your algorithm compared to the previous question

Answer 1

Answer:

Algorithm explained below

Explanation:

Algorithm to check duplicate when list of element is sorted:

CheckDuplicate( Sorted list )

    initialize count = 0

    Repeat untill we reach on end of list :

            if next is not end of list and current element is equal to next element

                    count = count+1

                    increase the pointer to next untill a different element is found

end CheckDuplicate

Worst Case Time Complexity will be O(n). Because there is only one iteration over the list will be performed.

Yes We have improved the worst case time complexity compared to previous question.

Actually after applying sorting all the similar element to will be next to each other.Then we will start iterating one by one from one side and check which is similar to next.If a different element will be find then we will check whether it's next is similar to it or not.

eg. 1 1 1 2 2 2 4 4 4 we can check duplicate in one iteration.