Consider a procedure $find()$ which take array of $n$ integers as input, and produce pair of element of array whose difference is not greater than the difference of any other pair of element of that array. Which of the following represent worst case time complexity of $find()$ procedure??
$A)O(n)$ $B)O(nlogn)$ $C)O(n^{2})$ $D)O(n^{2}log n)$
Here we need to sort first and then need to compare adjacent element
right??
Then what will be complexity??
@itssandeepverma , @Punit Sharma , @coder_yash In any case whether it be absolute difference or the simple difference
then it would be O(n) complexity only right?
So according to me, the worst case time complexity will be 0(n^2)
the pseudo code is-------
find()
{ int B[n];
for ( int i=0; i<=n; i++ )
{
for ( int j=0; j<=n; j++)
int max= B[i] - B[j];
if( B[i] - B[j] <= max)
{ something}
else max= B[i] - B[j];
}
the two loops are running and number of comparisions made are (n-1)+ (n-2) + (n-3) + …...+2+1
worst case time complexity becomes 0(n^2)
64.3k questions
77.9k answers
244k comments
80.0k users