for a particular query it will be O(log n+k).Where k is the no. of elements to be reported.
On Wed, Mar 31, 2010 at 11:54 PM, BlackdiamonD <patidarc...@gmail.com> wrote: > Binary Indexed Trees or Segment Interval trees. building them also it will > take O(n log(n)) > ..i feel for a particular query it will be difficult less than O(n) .because > .u must know all the element. > > 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. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. > > > > -- > ~~~~BL/\CK_D!AMOND~~~~~~~~ > > -- > 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. > -- 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.
