For the second question its not possible to do it in O(log n), as u need O(n) time to read the elements itself. You need to check your second question. There might be some constraints associated with the arrays.
On 5/19/07, dor <[EMAIL PROTECTED]> wrote: > > > 1. You can certainly do it in O(n log(n)) without any additional > memory. Sometimes you can bring the complexity down using additional > memory (i.e., hashing). > > 2. O(n log(n)) is trivial (sorting). There is a linear time algorithm > for finding the median (I call it "median of the medians", I don't > know if it has a specific name). Here is a good description of the > algorithm (see "Linear Selection" section): > > http://www.cs.princeton.edu/courses/archive/spring06/cos423/Handouts/notes%20on%20heapsort.doc > > On May 18, 10:33 pm, alkispe <[EMAIL PROTECTED]> wrote: > > Hello everyone i have 2 problems and i need the best algorithms and > > the complexity. Can you please help me? > > > > 1. Find if in an array there are some elements that appear more than > > one times > > 2. You have 2 arrays A and B.give the best algorithm for finding the > > median of the 2n elements of the two arrays > > > > Also for the 2nd question i need an algorithm with complexity > > O(log(n)). > > > > Please help me > > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
