> > @All: Doing a sorting for O(n logn) and then binary search for x1 and x2 in > O(logn) will be less efficient than the simple solution of O(n). Think on > the data structure that can optimize it. > Is it possible in time complexity < O(n)? >
> If you want to do the operation just once then it cannot be done faster than O(n) time. Even the mentioned data structures require atleast O(n) amount of preprocessing. All the mentioned algorithms are available here http://www.topcoder.com/tc?d1=tutorials&d2=alg_index&module=Static Hope it helps On Wed, Mar 31, 2010 at 8:26 PM, Priyanka Chatterjee <dona.1...@gmail.com>wrote: > The list of N integers is not sorted. > The solution is asked for a particular query. > > @Abhijit Reddy: Can you elaborate more on* Binary Indexed Trees* or *Segment > Interval trees*. May be you opted for the correct data structure. Please > give the algorithm. > > @All: Doing a sorting for O(n logn) and then binary search for x1 and x2 in > O(logn) will be less efficient than the simple solution of O(n). Think on > the data structure that can optimize it. > Is it possible in time complexity < O(n)? > >> >> > > > -- > Thanks & Regards, > Priyanka Chatterjee > Third Year Undergraduate Student, > Computer Science & Engineering, > National Institute Of Technology,Durgapur > India > http://priyanka-nit.blogspot.com/ > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
