Please only do the first question and use pseudocode. Please type the answer, do
ID: 3749510 • Letter: P
Question
Please only do the first question and use pseudocode. Please type the answer, don't take the handwriting picture.
Please type the answer, don't take the handwriting picture.
Please type the answer, don't take the handwriting picture.
Please type the answer, don't take the handwriting picture.
Please type the answer, don't take the handwriting picture.
Please type the answer, don't take the handwriting picture.
1. Given a sequential list with n numbers, represented in a one dimensional array A)Write an algorithm to check if the list has any duplication Explain the time complexity of your algorithm Can you think of a better algorithm to do the job? If so, briefly explain B) Write an algorithm to find all the duplicate numbers in the list, if any. Explain the time complexity of your algorithm Can you think of a better algorithm to do the job? If so, briefly eXplainExplanation / Answer
1.a)
arr[] array containing n numbers.
any_duplicate(arr){
sort(arr) // O(n logn) using merge sort
for i =2 to n{
if(arr[i-1] ==arr[i]
// duplicate exist
Return true;
}
else
return false
}
Time complexity =
best case O(n.logn)
Worst case O(nlogn)
1.b)
arr[] array containing n numbers.
any_duplicate(arr){
sort(arr) // O(n logn) using merge sort
for i =2 to n{
if(arr[i-1] ==arr[i]
// duplicate exist
print(arr[i]) ;
}
}
Time complexity =
best case O(nlogn)
Worst case O(nlogn)
Another approach would be to use modified counting sort to count the occurrence of ANY number this will take O(n) but it requires knowledge of range of number exist in array and only works for integer array.
THUMBS UP IF YOU ARE SATISFIED WITH ANSWER OTHERWISE REPLY WITH YOUR CONCERN