@saurabh : right!! @Sangeeta : could you please clarify query raised by saurabh.
On Fri, Dec 16, 2011 at 3:42 PM, atul anand <[email protected]> wrote: > @arvind : and we want to find median in O(1) time not O(n). > > > On Fri, Dec 16, 2011 at 3:41 PM, atul anand <[email protected]>wrote: > >> @arvind: what doubt ????? .... given link is meadia-of median algorithm >> whose complexity would be O(n) in worst case.This can be used when input >> stream is not sorted but as per the question it is a sorted stream. >> >> >> On Fri, Dec 16, 2011 at 1:20 PM, arvind kumar <[email protected]>wrote: >> >>> Hi,have a look at this,n revert back in case of doubts: >>> http://www.cs.cmu.edu/~avrim/451/lectures/lect0903.pdf >>> >>> On Fri, Dec 16, 2011 at 12:56 PM, Sangeeta <[email protected]> >>> wrote: >>> > You are given a stream of numbers which can be positive or negative. >>> > You are >>> > required to provide an operation FIND MEDIAN..which when invoked >>> > should be >>> > able return the median of the numbers in stream (in sorted order) in >>> > O(1) >>> > time. >>> > >>> > -- >>> > You received this message because you are subscribed to the Google >>> Groups "Algorithm Geeks" group. >>> > To post to this group, send email to [email protected]. >>> > To unsubscribe from this group, send email to >>> [email protected]. >>> > For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> > >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Algorithm Geeks" group. >>> To post to this group, send email to [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]. >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >>> >> > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
