Re: [Bug-gnubg] OT: An algorithm problem

[Jim Segrave]

On Fri 09 Feb 2007 (13:54 +0100), Massimiliano Maini wrote:
> address@hidden wrote on 
> 09/02/2007 12:30:36:
> 
> > Hi,
> > 
> > As some of you may know I'm now taking an CS education. (At last). 
> > In an exercise in the course "Algorithm and complexity", I was faced
> > with this challenge:
> > 
> > Describe an algorithm that takes two ordered sets (implemented as 
> > arrays) S and T (no duplicates in the two sets) of size n, and k, to
> > find the k-th smallest key in the union of S and T. The running time
> > should be of order O(lg n).

This one is O(lg k). For n > k, one can simply ignore elements after k
in S, so it can't affect the running time.

I hate to say how annoyed I got with almost correct algorithms that
broke every once in a while (that's why there's a test for every pair
of n,k values n = 0..2000, k = 1..2000)

I tried to time this, but the setup time is so large compared to the
run time that I was unable to get any useful measurments - it was
running in a matter of microseconds per search on 1000 element arrays.

-- 
Jim Segrave           address@hidden

find-kth-smallest.py
Description: Text document