We are given a sorted array A[a..n] of arbitrary real numbers. For each I [1..n-

Question

We are given a sorted array A[a..n] of arbitrary real numbers. For each I [1..n-1], we call A[i+1]-A[i] the i-th gap of A. Note that there are n-1 gaps

a) The average gap of A is the average of the n-1 gaps of A. How fast can you compute the average gap of A? How?

b) By the law of averages there must be some I [a..n-1] such that the i-th gap of A does not exceed the average gap of A we call any such i-th gap a short gap. The problem is to find a short gap of A. There is an obvious O(n) time algorithm that checks each gap and picks the shortest one. Describe a asymptotically faster divide-and-conquer algorithm to find a short gap of A.

c) Explain the correctness of your algorithm in part(b)

d) Analyze the running time of your algorithm in part(b)

Explanation / Answer

for(k=0;k<n;k++)

{

igap[x]=number[k+1]-number[k];

sum=sum+igap[x];

x++;

}

Avg=sum/n-1;

printf("the average gap is %d",Avg);

}

The above code in order to compute average of n-1 gaps,it takes O(n)time since it takes n number of iterations in for loop.

Therefore, The running time of the above algorithm is O(n) time .

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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