# if in an unsorted array we have 1000 distinct elements…

0

if in an unsorted array we have 1000 distinct elements then what are the minimum number of comparisons needed to get second smallest elements in the array(worst case)..can any one give algorithm used here???

what will be the number of comparisons for largest will it be n-1 or some thing else

Ravi Garg edited question

0
Niraj Kant Sinha (anonymous)

Start with comparing elements of the array in odd and even positions and determining largest element of each pair. Now you’ve got only n/2 elements. Continue pairwise comparisons to get n/4, n/8, … elements. Stop when the largest element is found. This step requires n-1 comparisons.
During previous step, the largest element was immediately compared with log(n) other elements. You can determine the largest of these elements in log(n)-1 comparisons. That would be the second-largest number in the array.

Niraj Kant Sinha answered
0
Rahul Sharma (anonymous)

n + lg(n) – 2

0
Prathyusha Vasista (anonymous)

we can further do it in n-1 by maintaining an array for the elements which we swap whenever we find a smallest element. n-1 comparisons are required for such an array and in that array the element in last but 1 position is the second smallest. cant we do it this way when space is not of concern??? pls correct me

0

how the second smallest element will be found by n+log n -2 .formula..know

0
Ankit Chauhan (anonymous)

See the conment by Niraj Kant Sinha u will understand he defined execellently

### Question stats

• Active
• Views624 times