You can do a lot better than N log(N). Don On Wednesday, October 9, 2013 2:03:02 PM UTC-4, hppygrry wrote: > > What's wrong with just a simple approach with checking the values in the > array[s] ? Since its already sorted, it takes log(s) time. Assuming S > approaches N, we are still only looking at N log (N). > > > > On Tuesday, October 8, 2013 11:24:54 AM UTC-7, atul007 wrote: >> >> can't we use idea of reservoir sampling here ? >> >> >> On Tue, Oct 8, 2013 at 8:18 PM, Don <dond...@gmail.com> wrote: >> >>> Provide a function which returns a value randomly and uniformly selected >>> from the range 0..N-1 excluding values in the array a[S] containing sorted >>> values in the same range. A rejection algorithm would work well enough if S >>> is much smaller than N, but what if N is large and S is slightly smaller? >>> >>> Assume that you are given a pseudo-random generator int rnd(int n) which >>> returns a pseudo-random number uniformly distributed in the range 0..n-1. >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Algorithm Geeks" group. >>> To unsubscribe from this group and stop receiving emails from it, send >>> an email to algogeeks+...@googlegroups.com. >>> >> >>
-- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
