Sunday, June 27, 2010

Find the second smallest number in an array A

A is an array of integers. Optimal in time and space


  1. Simple Algorithm: Walk thru' the list keeping track of smallest and second smallest numbers... Runs in O(n) time.

    A second alternative is use Median Of Median algorithm that guarantees the ability to return kth smallest element in O(n).