oh sorry, yeah its O(nlgn) On Thu, Apr 1, 2010 at 9:27 PM, BlackdiamonD <patidarc...@gmail.com> wrote:
> @Navin Naidu: you are wrong in your preprocessing it will take log(n) for > insertion in red black so > creating a red black it will take O(n log n) > who it is O(n)....? > > On Thu, Apr 1, 2010 at 1:50 PM, Navin Naidu <navinmna...@gmail.com> wrote: > >> I think preprocessing time of O(n) will be required to construct the data >> structure. >> >> *Data Structure used:* R-B tree. >> * >> The additional data that will be stored in each node is : * >> a) the size of subtree at each node >> b) parent node. >> >> *New Query:* >> Find the kth element in the tree: Complexity will be O(lgn) >> >> >> So the total complexity to find all the values between x1 and x2 will be: >> >> complexity to find x1 + complexity to find x2 + finding all the values >> between these two points (this includes finding LCA) = O(lgn) + O(lgn) + >> O(lgn) = O(lgn) >> >> preprocessing time : O(n) >> complexity of query : O(lgn) >> >> >> >> >> 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<algogeeks%2bunsubscr...@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<algogeeks%2bunsubscr...@googlegroups.com> >>> . >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> >> >> -- >> Thanks & Regards, >> >> - NMN >> >> -- >> 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. >> > > > > -- > ~~~~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<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Thanks & Regards, - NMN -- 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.
