[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Bug-gnubg] OT: An algorithm problem
From: |
Øystein Johansen |
Subject: |
Re: [Bug-gnubg] OT: An algorithm problem |
Date: |
Fri, 09 Feb 2007 14:12:25 +0100 |
>> 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).
>
> Hmmm ... O(lg n) or O(lg k) ?
k must be in the same order as n. Assuming that k =< n (*), you can actually do
a initial step; reducing the two set to k elements and then finding the median
in these two k sized elements.
(*) if (n < k < 2n) you flip the question. Find the (2n-k)-th largest element
in the union of S and T. That should work, shouldn't it?
-Øystein