On 11 April 2010 21:56, 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 the solution
> Median of medians is a decent algorithm for extracting the kth element( an
> element of kth rank ).
>
I asked to find all elements with rank 1 to k (kth smallest elements)
which would take O(kn). I was looking forward to innovative approaches other
than what stated in Cormen.
--------------------------------------------------
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 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 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>>
