[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

**
**`find-kth-smallest.py`

*Description:* Text document