[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Jim Segrave
Subject: Re: [Bug-gnubg] OT: An algorithm problem
Date: Wed, 14 Feb 2007 13:25:28 +0100
User-agent: mutt-ng/devel-r804 (FreeBSD)

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

Attachment: find-kth-smallest.py
Description: Text document

reply via email to

[Prev in Thread] Current Thread [Next in Thread]