Consider the following algorithm for finding the distance between the two closes

Question

Consider the following algorithm for finding the distance between the two closest elements in an array of numbers.

Algorithm MinDistance(A[0..n 1])

//Input: Array A[0..n 1] of numbers

//Output: Minimum distance between two of its elements

dmin

for i 0 to n 1 do

for j 0 to n 1 do

if i j and sqrt( (A[i] A[j])^2 )< dmin

dmin sqrt( (A[i] A[j])^2 )

return dmin

(a) What is the basic operation of this algorithm? For the worst case, how many times is it performed as a function of the array size n? How about the best case?

Explanation / Answer

Answer:

Basic operation of this algorithm:
-- If list of array A[]={12,22,90,17,21} then “MinDistance()” take parameter of A[]
-- Then each of outer and inner for loops checks for disance from 0th element to n-1th element
-- Example during pass-1 distance between value 12 to 2 is finding, then “dmin” is sqrt(12-17)^2 is 05
-- This finding minimum distance is done for all elements and final lowest “dmin” is returned

Worst case:
-- If n no.of elements there will be n-no.of times outer loop i, n-no.of times inner loop j
-- So the complexity of worst case is:    f(n) =n(n+1)

Best case:
-- If n no.of elements there will be first comparision itself between 0th and 1st elements is minimum then best case is : f(n)=1

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.