if in an unsorted array we have 1000 distinct elements…


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
    Aaditya Sharma (anonymous)

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

    Aaditya Sharma answered
      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
        Rahul Sharma (anonymous)

        n + lg(n) – 2

        Rahul Sharma answered
          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
            Ankit Chauhan (anonymous)

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

            Ankit Chauhan answered
              Add image to editor add image from link

              Question stats

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