Re: [algogeeks] Re: Suggest Algo for this Question
Nice Soln Lucifer, i had problem of tracking kth value when coming across two siblings, each sibling has many childs so i think a bottom up approach would be better for finding number of elements(say* y*) x finally at root we have y, if y=k then kth element is x else kth elemnt is x Surender On Sun, Dec 18, 2011 at 12:49 AM, Lucifer sourabhd2...@gmail.com wrote: @atul.. Complexity would be 2(n-k+1) = O(2*(n-k)) Basically the condition based on which the traversal is performed willow change. I have modified some part of the original post to show that: Instead of having the initial count as K have it as N-K+1 .. when taking a max-heap.. To solve the problem we need to do a pre-order traversal keeping the following conditions in mind: (pass K and root node) 1) If current node is X then skip the processing of the tree rooted at the current node. 2) If current node is = X , then decrement the initial count i.e (n-k +1) by 1 and process its childs ( i.e take step 1 for rach child). The result will depend on: a) If at any stage recursion ends and the value of initial count 0 then the kth smallest element is X. b) If during tree traversal the value of initial count reaches 0, that means there are atleast (n-k+1) elements which are = X. Hence, at this point terminate the recursion ( as in no need to continue). This result signifies that the kth smallest element = X. On Dec 17, 1:28 pm, atul anand atul.87fri...@gmail.com wrote: @Lucifer : if for the same question , we consider a Max heap instead of Min heap then complexity of the same algo will be O(N) ... right??? On Fri, Dec 16, 2011 at 8:50 PM, Lucifer sourabhd2...@gmail.com wrote: @my previous post.. While explaining the run-time I have made an editing mistake... instead of 'N' nodes it should be 'K' nodes.. i.e. Hence, for any given bin- tree having 'K' nodes, the number of null nodes is 'K+1'. These null nodes are nothing but the nodes where the check nodeValue X failed while traversing the original tree. Hence, the total number of checks will be 2K+1 = O(2K) On Dec 16, 1:04 am, sunny agrawal sunny816.i...@gmail.com wrote: oops... wanted to write the same but yeah its meaning turns out to be totally different :( anyways very well explained by Lucifier @shashank i think now u will be able to get why there will be only 2k comparisons in the worst case On Thu, Dec 15, 2011 at 10:51 PM, atul anand atul.87fri...@gmail.com wrote: @Lucifer : yes even i found flaw in the above algo when i gave it a second thought but didnt get time to post it. bcoz min heap has property that the parent node is less than its both child(subtree to be more precise ) but it does not confirm that left child is always smaller than right child of the node. On Thu, Dec 15, 2011 at 10:31 PM, Lucifer sourabhd2...@gmail.com wrote: @All I don't think the algo given above is entirely correct.. Or may be i didn't it properly... So basically say a preorder traversal of the heap is done based on whether the current root value X. As the algo says that at any point if k0 and we hit a node value which is =X , then we are done. If i understood it properly then thats not correct. The reason being that say on the left subtree we end up at a node whose value is =x and say k 0. Now until and unless we don't parse the right subtree (or basically the right half which was neglected as part of pre-order traversal or say was to be considered later) we are not sure if the current node is actually withing the first smallest K nos. It may happen that previously neglected (or rather later to be processed) half has the kth smallest element which is actually X. The reason being that a heap is not a binary search tree where there is a strict relation between the left and the right half so that we can say that if say a condition P is true in the left half then it will be false in the right half and vice versa. To solve the problem we need to do a pre-order traversal keeping the following conditions in mind: (pass K and root node) 1) If current node is = X then skip the processing of the tree rooted at the current node. 2) If current node is X , then decrement K by 1 and process its childs ( i.e take step 1 for rach child). The result will depend on: a) If at any stage recursion ends and the value of K0 then the kth smallest element is = X. b) If during tree traversal the value of K reaches 0, that means there are atleast k elements which are X. Hence, at this point terminate the recursion ( as in no need to continue). This result signifies that the kth smallest element X. Therefore to generalize... Perform a preorder traversal for
Re: [algogeeks] Re: Suggest Algo for this Question
@Lucifer : if for the same question , we consider a Max heap instead of Min heap then complexity of the same algo will be O(N) ... right??? On Fri, Dec 16, 2011 at 8:50 PM, Lucifer sourabhd2...@gmail.com wrote: @my previous post.. While explaining the run-time I have made an editing mistake... instead of 'N' nodes it should be 'K' nodes.. i.e. Hence, for any given bin- tree having 'K' nodes, the number of null nodes is 'K+1'. These null nodes are nothing but the nodes where the check nodeValue X failed while traversing the original tree. Hence, the total number of checks will be 2K+1 = O(2K) On Dec 16, 1:04 am, sunny agrawal sunny816.i...@gmail.com wrote: oops... wanted to write the same but yeah its meaning turns out to be totally different :( anyways very well explained by Lucifier @shashank i think now u will be able to get why there will be only 2k comparisons in the worst case On Thu, Dec 15, 2011 at 10:51 PM, atul anand atul.87fri...@gmail.com wrote: @Lucifer : yes even i found flaw in the above algo when i gave it a second thought but didnt get time to post it. bcoz min heap has property that the parent node is less than its both child(subtree to be more precise ) but it does not confirm that left child is always smaller than right child of the node. On Thu, Dec 15, 2011 at 10:31 PM, Lucifer sourabhd2...@gmail.com wrote: @All I don't think the algo given above is entirely correct.. Or may be i didn't it properly... So basically say a preorder traversal of the heap is done based on whether the current root value X. As the algo says that at any point if k0 and we hit a node value which is =X , then we are done. If i understood it properly then thats not correct. The reason being that say on the left subtree we end up at a node whose value is =x and say k 0. Now until and unless we don't parse the right subtree (or basically the right half which was neglected as part of pre-order traversal or say was to be considered later) we are not sure if the current node is actually withing the first smallest K nos. It may happen that previously neglected (or rather later to be processed) half has the kth smallest element which is actually X. The reason being that a heap is not a binary search tree where there is a strict relation between the left and the right half so that we can say that if say a condition P is true in the left half then it will be false in the right half and vice versa. To solve the problem we need to do a pre-order traversal keeping the following conditions in mind: (pass K and root node) 1) If current node is = X then skip the processing of the tree rooted at the current node. 2) If current node is X , then decrement K by 1 and process its childs ( i.e take step 1 for rach child). The result will depend on: a) If at any stage recursion ends and the value of K0 then the kth smallest element is = X. b) If during tree traversal the value of K reaches 0, that means there are atleast k elements which are X. Hence, at this point terminate the recursion ( as in no need to continue). This result signifies that the kth smallest element X. Therefore to generalize... Perform a preorder traversal for root node X, and keep decrementing the count K by 1. If K reaches 0 during traversal then end the recursion. After the call to the recursive traversal is over, check for the value of K. If greater than 0, then the kth smallest element = X otherwise its not. The time complexity will always be 2K ( in the worst case basically when K value reaches 0 ). If u analyze it closely we are making 2 checks when at particular node for its children. Hence, whether both the child nodes have value X or one of them or node, at the end we always end up making 2 checks for the children (left and right child). So given any tree one can think of a null node as a leaf node ( depicting that the node has a value =X) . Hence, for any given bin- tree having nodes 'N', the number null nodes is 'N+1'. Hence, the total number of checks will be 2N+1 = O(2N) , On Dec 15, 1:00 pm, WgpShashank shashank7andr...@gmail.com wrote: @sunny why we look at all k number which are greater then x , correct ? Lets think in this way we wants to check if kth smallest element in heap thats =x isn't it ? so if root of mean heap is greater then x then none other elements will less then x so we terminate . else our algorithm will search children of all the nodes which are less then x till either we have found k of them or we are exhausted e.g. when k=0 . so we will cal our function to both left right children ? so now think we are looking for children's of only nodes which are less then x and at most k of these in tottal . each have
Re: [algogeeks] Re: Suggest Algo for this Question
@sunny why we look at all k number which are greater then x , correct ? Lets think in this way we wants to check if kth smallest element in heap thats =x isn't it ? so if root of mean heap is greater then x then none other elements will less then x so we terminate . else our algorithm will search children of all the nodes which are less then x till either we have found k of them or we are exhausted e.g. when k=0 . so we will cal our function to both left right children ? so now think we are looking for children's of only nodes which are less then x and at most k of these in tottal . each have atmost two visited childrens so we have visted at-most 3K nodes isn;t it ? for total time O(K) ? let me know where i am wrong ? i am not getting for uy k nodes greater then x ? why we will do that then how much comparisons u needs for that ? Thanks Shashank Mani CSE, BIT Mesra http://shashank7s.blogspot.com/ -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/lsuMzgEQdMwJ. To post to this group, send email to algogeeks@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.
Re: [algogeeks] Re: Suggest Algo for this Question
@Lucifer : yes even i found flaw in the above algo when i gave it a second thought but didnt get time to post it. bcoz min heap has property that the parent node is less than its both child(subtree to be more precise ) but it does not confirm that left child is always smaller than right child of the node. On Thu, Dec 15, 2011 at 10:31 PM, Lucifer sourabhd2...@gmail.com wrote: @All I don't think the algo given above is entirely correct.. Or may be i didn't it properly... So basically say a preorder traversal of the heap is done based on whether the current root value X. As the algo says that at any point if k0 and we hit a node value which is =X , then we are done. If i understood it properly then thats not correct. The reason being that say on the left subtree we end up at a node whose value is =x and say k 0. Now until and unless we don't parse the right subtree (or basically the right half which was neglected as part of pre-order traversal or say was to be considered later) we are not sure if the current node is actually withing the first smallest K nos. It may happen that previously neglected (or rather later to be processed) half has the kth smallest element which is actually X. The reason being that a heap is not a binary search tree where there is a strict relation between the left and the right half so that we can say that if say a condition P is true in the left half then it will be false in the right half and vice versa. To solve the problem we need to do a pre-order traversal keeping the following conditions in mind: (pass K and root node) 1) If current node is = X then skip the processing of the tree rooted at the current node. 2) If current node is X , then decrement K by 1 and process its childs ( i.e take step 1 for rach child). The result will depend on: a) If at any stage recursion ends and the value of K0 then the kth smallest element is = X. b) If during tree traversal the value of K reaches 0, that means there are atleast k elements which are X. Hence, at this point terminate the recursion ( as in no need to continue). This result signifies that the kth smallest element X. Therefore to generalize... Perform a preorder traversal for root node X, and keep decrementing the count K by 1. If K reaches 0 during traversal then end the recursion. After the call to the recursive traversal is over, check for the value of K. If greater than 0, then the kth smallest element = X otherwise its not. The time complexity will always be 2K ( in the worst case basically when K value reaches 0 ). If u analyze it closely we are making 2 checks when at particular node for its children. Hence, whether both the child nodes have value X or one of them or node, at the end we always end up making 2 checks for the children (left and right child). So given any tree one can think of a null node as a leaf node ( depicting that the node has a value =X) . Hence, for any given bin- tree having nodes 'N', the number null nodes is 'N+1'. Hence, the total number of checks will be 2N+1 = O(2N) , On Dec 15, 1:00 pm, WgpShashank shashank7andr...@gmail.com wrote: @sunny why we look at all k number which are greater then x , correct ? Lets think in this way we wants to check if kth smallest element in heap thats =x isn't it ? so if root of mean heap is greater then x then none other elements will less then x so we terminate . else our algorithm will search children of all the nodes which are less then x till either we have found k of them or we are exhausted e.g. when k=0 . so we will cal our function to both left right children ? so now think we are looking for children's of only nodes which are less then x and at most k of these in tottal . each have atmost two visited childrens so we have visted at-most 3K nodes isn;t it ? for total time O(K) ? let me know where i am wrong ? i am not getting for uy k nodes greater then x ? why we will do that then how much comparisons u needs for that ? Thanks Shashank Mani CSE, BIT Mesrahttp://shashank7s.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. 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 algogeeks@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.
Re: [algogeeks] Re: Suggest Algo for this Question
oops... wanted to write the same but yeah its meaning turns out to be totally different :( anyways very well explained by Lucifier @shashank i think now u will be able to get why there will be only 2k comparisons in the worst case On Thu, Dec 15, 2011 at 10:51 PM, atul anand atul.87fri...@gmail.comwrote: @Lucifer : yes even i found flaw in the above algo when i gave it a second thought but didnt get time to post it. bcoz min heap has property that the parent node is less than its both child(subtree to be more precise ) but it does not confirm that left child is always smaller than right child of the node. On Thu, Dec 15, 2011 at 10:31 PM, Lucifer sourabhd2...@gmail.com wrote: @All I don't think the algo given above is entirely correct.. Or may be i didn't it properly... So basically say a preorder traversal of the heap is done based on whether the current root value X. As the algo says that at any point if k0 and we hit a node value which is =X , then we are done. If i understood it properly then thats not correct. The reason being that say on the left subtree we end up at a node whose value is =x and say k 0. Now until and unless we don't parse the right subtree (or basically the right half which was neglected as part of pre-order traversal or say was to be considered later) we are not sure if the current node is actually withing the first smallest K nos. It may happen that previously neglected (or rather later to be processed) half has the kth smallest element which is actually X. The reason being that a heap is not a binary search tree where there is a strict relation between the left and the right half so that we can say that if say a condition P is true in the left half then it will be false in the right half and vice versa. To solve the problem we need to do a pre-order traversal keeping the following conditions in mind: (pass K and root node) 1) If current node is = X then skip the processing of the tree rooted at the current node. 2) If current node is X , then decrement K by 1 and process its childs ( i.e take step 1 for rach child). The result will depend on: a) If at any stage recursion ends and the value of K0 then the kth smallest element is = X. b) If during tree traversal the value of K reaches 0, that means there are atleast k elements which are X. Hence, at this point terminate the recursion ( as in no need to continue). This result signifies that the kth smallest element X. Therefore to generalize... Perform a preorder traversal for root node X, and keep decrementing the count K by 1. If K reaches 0 during traversal then end the recursion. After the call to the recursive traversal is over, check for the value of K. If greater than 0, then the kth smallest element = X otherwise its not. The time complexity will always be 2K ( in the worst case basically when K value reaches 0 ). If u analyze it closely we are making 2 checks when at particular node for its children. Hence, whether both the child nodes have value X or one of them or node, at the end we always end up making 2 checks for the children (left and right child). So given any tree one can think of a null node as a leaf node ( depicting that the node has a value =X) . Hence, for any given bin- tree having nodes 'N', the number null nodes is 'N+1'. Hence, the total number of checks will be 2N+1 = O(2N) , On Dec 15, 1:00 pm, WgpShashank shashank7andr...@gmail.com wrote: @sunny why we look at all k number which are greater then x , correct ? Lets think in this way we wants to check if kth smallest element in heap thats =x isn't it ? so if root of mean heap is greater then x then none other elements will less then x so we terminate . else our algorithm will search children of all the nodes which are less then x till either we have found k of them or we are exhausted e.g. when k=0 . so we will cal our function to both left right children ? so now think we are looking for children's of only nodes which are less then x and at most k of these in tottal . each have atmost two visited childrens so we have visted at-most 3K nodes isn;t it ? for total time O(K) ? let me know where i am wrong ? i am not getting for uy k nodes greater then x ? why we will do that then how much comparisons u needs for that ? Thanks Shashank Mani CSE, BIT Mesrahttp://shashank7s.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. 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 algogeeks@googlegroups.com. To unsubscribe from this
Re: [algogeeks] Re: Suggest Algo for this Question
i am Considering given heap as min heap Sol - because heap has property that root will has lower value than all the elements in its left sub tree and right sub tree so in main we will call a function passing root and value k and x if at any time root is greater than x and k 0 that means rest of the elements are greater than x so kth is also greater than x else make recursive calls for both of its child as soon as k hits zero in any recursive call we know that there are k elements less than x. i think in worst case 2k comparisons will be there hence O(k) On Wed, Dec 14, 2011 at 12:24 PM, atul anand atul.87fri...@gmail.comwrote: yup rite...it should be O(k log n ) not O(n log n). On Wed, Dec 14, 2011 at 11:44 AM, Dave dave_and_da...@juno.com wrote: @Atul: The initial heap is given. You have to maintain the heap property as k elements are removed, which is O(k log n). This does not satisfy the original request for an algorithm that is O(k) in the worst-case, independent of the size of the heap. Dave On Dec 13, 10:31 pm, atul anand atul.87fri...@gmail.com wrote: @gaurav : you need to first build heap and then maintain heap property ever time you remove element.so this would take O(n logn ). On Wed, Dec 14, 2011 at 1:38 AM, Gaurav Kumar gkuma...@gmail.com wrote: Why can't we keep removing the minimum element each time and compare it with x? This should take O(k) time since in a Min heap, the minimum element can be removed in O(1) time? Am I missing something? On Tue, Dec 13, 2011 at 8:43 AM, atul anand atul.87fri...@gmail.com wrote: O(k) in the worst-case , then i guess it would better to use median-of median algo to find element at rank k. and comparing with x. or we can us hashtable to solve this. On Tue, Dec 13, 2011 at 3:23 PM, Ankur Garg ankurga...@gmail.com wrote: Given an array-based heap on n elements and a real number x, efficiently determine whether the kth smallest element in the heap is greater than or equal to x. Your algorithm should be O(k) in the worst-case, independent of the size of the heap. This question was also asked in Amazon -- 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. 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 algogeeks@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 algogeeks@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 algogeeks@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 algogeeks@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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Suggest Algo for this Question
@sunny : this will work :) On Wed, Dec 14, 2011 at 4:08 PM, sunny agrawal sunny816.i...@gmail.comwrote: i am Considering given heap as min heap Sol - because heap has property that root will has lower value than all the elements in its left sub tree and right sub tree so in main we will call a function passing root and value k and x if at any time root is greater than x and k 0 that means rest of the elements are greater than x so kth is also greater than x else make recursive calls for both of its child as soon as k hits zero in any recursive call we know that there are k elements less than x. i think in worst case 2k comparisons will be there hence O(k) On Wed, Dec 14, 2011 at 12:24 PM, atul anand atul.87fri...@gmail.comwrote: yup rite...it should be O(k log n ) not O(n log n). On Wed, Dec 14, 2011 at 11:44 AM, Dave dave_and_da...@juno.com wrote: @Atul: The initial heap is given. You have to maintain the heap property as k elements are removed, which is O(k log n). This does not satisfy the original request for an algorithm that is O(k) in the worst-case, independent of the size of the heap. Dave On Dec 13, 10:31 pm, atul anand atul.87fri...@gmail.com wrote: @gaurav : you need to first build heap and then maintain heap property ever time you remove element.so this would take O(n logn ). On Wed, Dec 14, 2011 at 1:38 AM, Gaurav Kumar gkuma...@gmail.com wrote: Why can't we keep removing the minimum element each time and compare it with x? This should take O(k) time since in a Min heap, the minimum element can be removed in O(1) time? Am I missing something? On Tue, Dec 13, 2011 at 8:43 AM, atul anand atul.87fri...@gmail.com wrote: O(k) in the worst-case , then i guess it would better to use median-of median algo to find element at rank k. and comparing with x. or we can us hashtable to solve this. On Tue, Dec 13, 2011 at 3:23 PM, Ankur Garg ankurga...@gmail.com wrote: Given an array-based heap on n elements and a real number x, efficiently determine whether the kth smallest element in the heap is greater than or equal to x. Your algorithm should be O(k) in the worst-case, independent of the size of the heap. This question was also asked in Amazon -- 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. 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 algogeeks@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 algogeeks@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 algogeeks@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 algogeeks@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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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. 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 algogeeks@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.
Re: [algogeeks] Re: Suggest Algo for this Question
@sunny it will 3k not 2k ? u forgot to count the root element so over all time complexity will O(3K)=O(K) correct me if am wrong ? Thanks Shashank Mani CSE, BIT Mesra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/zDswz5losVUJ. To post to this group, send email to algogeeks@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.
Re: [algogeeks] Re: Suggest Algo for this Question
more clarification , why number of comparisons are 3k , because we are looking for only those nodes which are less then x and each nodea can max 2 childs , so tottal 3k comparisons . so it will O(3K) . Thanks Shashank CSE , BIT Mesra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/OALJEqbuE_MJ. To post to this group, send email to algogeeks@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.
Re: [algogeeks] Re: Suggest Algo for this Question
@shashank nope only 2k comparisions k numbers which are greater than x and k which are less than x dont think in terms of root and child On Thu, Dec 15, 2011 at 12:57 PM, WgpShashank shashank7andr...@gmail.comwrote: more clarification , why number of comparisons are 3k , because we are looking for only those nodes which are less then x and each nodea can max 2 childs , so tottal 3k comparisons . so it will O(3K) . Thanks Shashank CSE , BIT Mesra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/OALJEqbuE_MJ. To post to this group, send email to algogeeks@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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
