rarray A is as follows: A-12,20, 35, 28, 45, 23, 67,21, 95, 15 Your program (or
ID: 3700107 • Letter: R
Question
rarray A is as follows: A-12,20, 35, 28, 45, 23, 67,21, 95, 15 Your program (or pseudo-code) will find the indices of closest numbers in the array. In the above array A, 20 and 21 are the closest pairs. 1.b) Perform a complexity analysis of your algorithm as I did in the video tutorial. What is the best-case, average-case, and the worst-case scenarios? 2.a) Write a pseudo-code for "binary search" problem. In this problem, you will search an element in a sorted array. For example: A [1, 4, 7, 9, 12, 24, 56, 61, 62, 65, 89) If the search element is 12, your algorithm must find its index. Perform a complexity analysis for your algorithm as I did in the video tutorial. What is the best, average, and worst case? No code submission over Canvas is necessary. Please submit your solutions to the Canvas on due date as Word or Pdf file. On the top of your paper, please add your name and number, Course ID, Assignment number and the date.Explanation / Answer
1.
a) Algorithm to find indices of closest numbers:
Input: Array A[1,2,...n] of integers.
Output: indices x,y such thar A[x], A[y] is closest pair in A.
1.Sort the array A and store result in B using heap sort.
2. difference=B[2]-B[1]
3. index=1
4. for i=2 to n
5. if(B[i+1]-B[i]<difference)
6. difference=B[i+1]-B[i]
7. index=i.
8. return indeices of B[i] and B[i-1] in A.
b) Running time: step 1 takes O(nlog n) time,
step 2-8 takes O(n) time
so overall time complexity of this algorithm is: O(nlog n).
Best case: as best case of heap sort is O(n), so best case of algorithmis O(n).
Average case and worst case is: O(nlog n)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.