January 30, 2009

Finding Second Smallest Element

Jargon: Order Statistics problem is to find the kth smallest element in an unsorted array A[1..n]. This problem can be solved in O(n) time in average case using randomized select algorithm or in O(n) time in worst case time using an algorithm that chooses the pivot element carefully.

Problem: How to find second smallest element in an array A[1..n] of size n. We would like to do in much less than 2n comparisons.

Answer: Time Complexity = n + ceil(log n) - 2

Solution: show

Code for n + log n - 2 algorithm: second_smallest.py
Alternate implementation using linked list: second_smallest_linkedlist.py

6 comments:

  1. Great article! And it becomes so easy to code it with Python. In fact, a certain company gave reference to your blog and asked to solve the problem.

    ReplyDelete
  2. I encountered this problem as an exercise in CLRS and failed to figure out where the lg(n) come from. The phrase "knocked out by 1" explains everything.
    Thank you.

    ReplyDelete
  3. I am sorry, I am not sure if I understand this. What happens when the input array is sorted?

    {1, 2, 3, 4}

    Won't the algorithm fail?

    ReplyDelete
  4. Ignore my comment. I was wrong.

    ReplyDelete
  5. The tournament approach sounds like a great idea because the number of comparisons made is very small, but the other half of the story is that you are doing about N memory writes as opposed to no memory writes (if you kept just the top 2 values, those would likely end up being in registers), and you are using extra space. In practice, I would be surprised if this approach could outperform a naive implementation that just maintains the top 2 values at all times.

    ReplyDelete
  6. Hi Anon. A naive approach would be fine if cost of comparison is small.

    Imagine that the N items are database transactions and a comparison cost is large (say date comparison + string matching + expression evaluations). Then tournament approach makes more sense.

    Again I am making cases but the solution is interesting mostly from academic point-of-view.

    ReplyDelete