Oh yes.Median of medians selection algo is with the best complexity O(n). anythin else?
On Mon, Apr 12, 2010 at 7:51 PM, Rohit Saraf <rohit.kumar.sa...@gmail.com>wrote: > Find the kth element using order statistics - O(n) <> As far as i know , > u will have to use median of medians selection algorithm for this... > Rest is fine.. > > -------------------------------------------------- > Rohit Saraf > Second Year Undergraduate, > Dept. of Computer Science and Engineering > IIT Bombay > http://www.cse.iitb.ac.in/~rohitfeb14 > > > On Mon, Apr 12, 2010 at 3:20 PM, souri datta <souri.isthe...@gmail.com>wrote: > >> Steps: >> 1. Find the kth element using order statistics - O(n) >> 2. In one pass over the array, get all the elems less than the kth >> element. >> >> Let me know if this is not correct. >> >> >> >> On Mon, Apr 12, 2010 at 1:57 PM, Rohit Saraf < >> rohit.kumar.sa...@gmail.com> wrote: >> >>> I have already given an O(n) solution. See above ! >>> >>> The BST solution is O(nlogn) but is practically more nice. :) >>> >>> -------------------------------------------------- >>> Rohit Saraf >>> Second Year Undergraduate, >>> Dept. of Computer Science and Engineering >>> IIT Bombay >>> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >>> >>> >>> On Mon, Apr 12, 2010 at 1:16 PM, Nikhil Agarwal < >>> nikhil.bhoja...@gmail.com> wrote: >>> >>>> >>>> >>>> On Mon, Apr 12, 2010 at 12:58 PM, Rohit Saraf < >>>> rohit.kumar.sa...@gmail.com> wrote: >>>> >>>>> are yaar... i meant BST... i thought that was obvious ! >>>>> sry if i confused you.... >>>>> >>>> >>>> @rohit It's ok.Actually in this group people come up with very different >>>> and non-common solutions so its risky to take things 'obviously'. >>>> Rotation algo has a complexity of O(nlogn)[for constructing a BST] +O(n) >>>> [for rotating n times]=O(nlogn) . >>>> >>>> Till now best algo we have is using heaps which give rise to complexity >>>> = O(n+klogn) >>>> >>>> Please pass on algos having better runtime complexity. >>>> >>>>> >>>>> >>>>> -------------------------------------------------- >>>>> Rohit Saraf >>>>> Second Year Undergraduate, >>>>> Dept. of Computer Science and Engineering >>>>> IIT Bombay >>>>> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >>>>> >>>>> >>>>> On Mon, Apr 12, 2010 at 12:38 PM, Nikhil Agarwal < >>>>> nikhil.bhoja...@gmail.com> wrote: >>>>> >>>>>> Hey rohit.You were referring to Binary tree.Search keyword was >>>>>> missing.Because rotation makes no sense in binary tree.Please note binary >>>>>> tree and BST are different. >>>>>> >>>>>> On Mon, Apr 12, 2010 at 12:33 PM, Rohit Saraf < >>>>>> rohit.kumar.sa...@gmail.com> wrote: >>>>>> >>>>>>> Read the slides i uploaded. They explain what rotation does in a BST. >>>>>>> >>>>>>> Also you might like to refer to Red Black Trees in CLRS.... that >>>>>>> chapter explains rotations. >>>>>>> >>>>>>> -------------------------------------------------- >>>>>>> Rohit Saraf >>>>>>> Second Year Undergraduate, >>>>>>> Dept. of Computer Science and Engineering >>>>>>> IIT Bombay >>>>>>> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >>>>>>> >>>>>>> >>>>>>> On Mon, Apr 12, 2010 at 8:18 AM, Rohit Saraf < >>>>>>> rohit.kumar.sa...@gmail.com> wrote: >>>>>>> >>>>>>>> but still the binary tree solution is of more practical use.i will >>>>>>>> explain the solution once i reach my comp >>>>>>>> >>>>>>>> >>>>>>>> On 4/11/10, Nikhil Agarwal <nikhil.bhoja...@gmail.com> wrote: >>>>>>>> > >>>>>>>> > >>>>>>>> > On Sun, Apr 11, 2010 at 9:56 PM, Rohit Saraf < >>>>>>>> rohit.kumar.sa...@gmail.com> >>>>>>>> > wrote: >>>>>>>> >> >>>>>>>> >> Time complexity is O(n log n). But the last solution I gave has >>>>>>>> O(n). >>>>>>>> >> >>>>>>>> >> What did u not understand abt thesolution >>>>>>>> > >>>>>>>> > >>>>>>>> > @Rohit Please explain how that Binary tree solution works. >>>>>>>> >> >>>>>>>> >> >>>>>>>> >> -------------------------------------------------- >>>>>>>> >> Rohit Saraf >>>>>>>> >> Second Year Undergraduate, >>>>>>>> >> Dept. of Computer Science and Engineering >>>>>>>> >> IIT Bombay >>>>>>>> >> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >>>>>>>> >> >>>>>>>> >> >>>>>>>> >> On Sun, Apr 11, 2010 at 11:00 AM, Priyanka Chatterjee >>>>>>>> >> <dona.1...@gmail.com> wrote: >>>>>>>> >>> >>>>>>>> >>> >>>>>>>> >>> >>>>>>>> >>> On 11 April 2010 10:46, Rohit Saraf < >>>>>>>> rohit.kumar.sa...@gmail.com> wrote: >>>>>>>> >>>> >>>>>>>> >>>> Construct a binary tree from the data (maintain the size of >>>>>>>> subtree >>>>>>>> >>>> under each node). >>>>>>>> >>>> Do rotations till the left subtree does not have size k. >>>>>>>> Rotation is a >>>>>>>> >>>> constant time operation. >>>>>>>> >>>> Please prove the correctness of your algorithm with the time >>>>>>>> complexity >>>>>>>> >>>> >>>>>>>> >>>> -------------------------------------------------- >>>>>>>> >>>> Rohit Saraf >>>>>>>> >>>> Second Year Undergraduate, >>>>>>>> >>>> Dept. of Computer Science and Engineering >>>>>>>> >>>> IIT Bombay >>>>>>>> >>>> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >>>>>>>> >>>> >>>>>>>> >>>> >>>>>>>> >>>> >>>>>>>> >>>> On Mon, Mar 29, 2010 at 11:15 AM, blackDiamond < >>>>>>>> patidarc...@gmail.com> >>>>>>>> >>>> wrote: >>>>>>>> >>>>> >>>>>>>> >>>>> nice solution appreciate it. but your algorithm is wasting >>>>>>>> time in >>>>>>>> >>>>> finding all the element... >>>>>>>> >>>>> instead of that just find boundary line kth element which can >>>>>>>> help as >>>>>>>> >>>>> in finding element greater that kth and element small than kth >>>>>>>> and that >>>>>>>> >>>>> soluton can be done in O(N) >>>>>>>> >>>>> >>>>>>>> >>>>> >>>>>>>> >>>>> On Sun, Mar 28, 2010 at 10:02 PM, CHERUVU JAANU REDDY >>>>>>>> >>>>> <jaanu.cher...@gmail.com> wrote: >>>>>>>> >>>>>> >>>>>>>> >>>>>> >>>>>>>> >>>>>> 1) Construct max heap by taking first k elements in an array >>>>>>>> >>>>>> 2) if k+1 element less than root of max heap >>>>>>>> >>>>>> a) Delete root of max heap >>>>>>>> >>>>>> b) Insert k+1 element in max heap and apply heapify >>>>>>>> method >>>>>>>> >>>>>> 3) else skip the element >>>>>>>> >>>>>> 4) apply above procedure for all n elements in an array >>>>>>>> >>>>>> >>>>>>>> >>>>>> At last you will get k smallest elements and root is kth >>>>>>>> smallest >>>>>>>> >>>>>> element in the array >>>>>>>> >>>>>> >>>>>>>> >>>>>> this is O(nlogk) >>>>>>>> >>>>>> >>>>>>>> >>>>>> >>>>>>>> >>>>>> >>>>>>>> >>>>>> ---------------------------------------- >>>>>>>> >>>>>> CHERUVU JAANU REDDY >>>>>>>> >>>>>> M.Tech in CSIS >>>>>>>> >>>>>> >>>>>>>> >>>>>> >>>>>>>> >>>>>> On Sun, Mar 28, 2010 at 8:41 PM, abhijith reddy >>>>>>>> >>>>>> <abhijith200...@gmail.com> wrote: >>>>>>>> >>>>>>> >>>>>>>> >>>>>>> Can any one tell how to do this when there are 'm' queries >>>>>>>> like >>>>>>>> >>>>>>> "query i j k" find the kth largest element in between >>>>>>>> indices i->j in >>>>>>>> >>>>>>> an array. >>>>>>>> >>>>>>> When m is large even an O(n) algorithm would be slow. >>>>>>>> >>>>>>> I thinking that each query could be answered in O(sqrt(n)) >>>>>>>> time >>>>>>>> >>>>>>> So any suggestions ? >>>>>>>> >>>>>>> >>>>>>>> >>>>>>> Thanks >>>>>>>> >>>>>>> >>>>>>>> >>>>>>> >>>>>>>> >>>>>>> On Sun, Mar 28, 2010 at 7:57 PM, blackDiamond < >>>>>>>> patidarc...@gmail.com> >>>>>>>> >>>>>>> wrote: >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> there are better solution of O(n) are posted in the >>>>>>>> thread.......[?]. >>>>>>>> >>>>>>>> using order statices .... >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> On Sun, Mar 28, 2010 at 6:49 PM, Mukesh Kumar thakur >>>>>>>> >>>>>>>> <mukeshraj8...@gmail.com> wrote: >>>>>>>> >>>>>>>>> >>>>>>>> >>>>>>>>> Create a temp array temp[0..k-1] of size k. >>>>>>>> >>>>>>>>> 2) Traverse the array arr[k..n-1]. While traversing, keep >>>>>>>> updating >>>>>>>> >>>>>>>>> the smallest element of temp[] >>>>>>>> >>>>>>>>> 3) Return the smallest of temp[] >>>>>>>> >>>>>>>>> Time Complexity: O((n-k)*k). >>>>>>>> >>>>>>>>> >>>>>>>> >>>>>>>>> >>>>>>>> >>>>>>>>> try it ..............for this problem[?] >>>>>>>> >>>>>>>>> >>>>>>>> >>>>>>>>> -- >>>>>>>> >>>>>>>>> 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. >>>>>>>> >>>>>>> >>>>>>>> >>>>>>> >>>>>>>> >>>>>>> -- >>>>>>>> >>>>>>> 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<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. >>>>>>>> >>>> >>>>>>>> >>>> >>>>>>>> >>>> -- >>>>>>>> >>>> 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, >>>>>>>> >>> 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 algogeeks@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<algogeeks%2bunsubscr...@googlegroups.com> >>>>>>>> . >>>>>>>> >> For more options, visit this group at >>>>>>>> >> http://groups.google.com/group/algogeeks?hl=en. >>>>>>>> > >>>>>>>> > >>>>>>>> > >>>>>>>> > >>>>>>>> > -- >>>>>>>> > Thanks & Regards >>>>>>>> > Nikhil Agarwal >>>>>>>> > Junior Undergraduate >>>>>>>> > Computer Science & Engineering, >>>>>>>> > National Institute Of Technology, Durgapur,India >>>>>>>> > http://tech-nikk.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. >>>>>>>> > >>>>>>>> >>>>>>>> >>>>>>>> -- >>>>>>>> >>>>>>>> -------------------------------------------------- >>>>>>>> Rohit Saraf >>>>>>>> Second Year Undergraduate, >>>>>>>> Dept. of Computer Science and Engineering >>>>>>>> IIT Bombay >>>>>>>> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >>>>>>>> >>>>>>> >>>>>>> -- >>>>>>> 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 >>>>>> Nikhil Agarwal >>>>>> Junior Undergraduate >>>>>> Computer Science & Engineering, >>>>>> National Institute Of Technology, Durgapur,India >>>>>> http://tech-nikk.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<algogeeks%2bunsubscr...@googlegroups.com> >>>>> . >>>>> For more options, visit this group at >>>>> http://groups.google.com/group/algogeeks?hl=en. >>>>> >>>> >>>> >>>> >>>> -- >>>> Thanks & Regards >>>> Nikhil Agarwal >>>> Junior Undergraduate >>>> Computer Science & Engineering, >>>> National Institute Of Technology, Durgapur,India >>>> http://tech-nikk.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<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<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<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Thanks & Regards Nikhil Agarwal Junior Undergraduate Computer Science & Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.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.
<<338.gif>>
<<361.gif>>
