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.
