Let A[1], A[2],...,A[n] be an array containing positive integers. a) Describe an

ID: 3566648 • Letter: L

Question

Let A[1], A[2],...,A[n] be an array containing positive integers.

a) Describe an efficient algorithm to find the maximum difference between any two integers in the array. In other words, compute M=max1<= i, j <=n {A[i] - A[j]}. What is the running time of your algorithm? Explain. Use the O notation.

b) Describe an efficient algorithm to find the minimum positive difference between any two integers in the array. In orther words, compute m=min1<= i, j <=n { | A[i] - A[j] | }. What is the running time of your algorithm? Explain. Use the O notation.

Hint: I will give full points for an O(n) running time for (a) and for an O(nlogn) running time for (b).

Explanation / Answer

#include<stdio.h>

/* The function assumes that there are at least two

elements in array.

The function returns a negative value if the array is

sorted in decreasing order.

Returns 0 if elements are equal */

int maxDiff(int arr[], int arr_size)

{

int max_diff = arr[1] - arr[0];

int min_element = arr[0];

int i;

for(i = 1; i < arr_size; i++)

{

if(arr[i] - min_element > max_diff)

max_diff = arr[i] - min_element;

if(arr[i] < min_element)

min_element = arr[i];

}

return max_diff;

}

/* Driver program to test above function */

int main()

{

int arr[] = {1, 2, 6, 80, 100};

int size = sizeof(arr)/sizeof(arr[0]);

printf("Maximum difference is %d", maxDiff(arr, size));

getchar();

return 0;

}

Time Complexity: O(n)

Couldn't find time to code it.

Pseudo code :

TIME COMPLEXITY : O(n log n)