in Algorithms
2,018 views
6 votes
6 votes

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??

in Algorithms
by
2.0k views

4 Comments

yeah it should be order of n only!
0
0
I think they are asking for absolute difference.

Otherwise, Let say answer pair is {a,b},

Now what will be difference, a-b or b-a.

So to remove this ambiguity , I think absolute difference should be taken.
0
0

@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? 

 

0
0

1 Answer

0 votes
0 votes

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)

Related questions

0 votes
0 votes
1 answer
4