2,032 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??

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
0 answers
3
0 votes
0 votes
1 answer
4