[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?


reply via email to

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