# 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

### 7 answers

0
Ankit Chauhan (anonymous)

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

Ankit Chauhan answered
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

Rahul Sharma answered
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

Prathyusha Vasista answered
0
Aaditya Sharma (anonymous)

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

Aaditya Sharma answered
Add image to editor add image from link

### Question stats

• Active
• Views700 times
• Answers7 answers
• Followers1 follower
Question and answer is powered by AnsPress