@Shachindra If you are using binary tree then why are you doing sorting first?
@ANKIT Yes you can't do searching of sum of two numbers in less then O(n*n). On Tue, Jun 28, 2011 at 6:23 PM, Shachindra A C <sachindr...@gmail.com>wrote: > @ankit : I'm pretty confident that the second part of your solution cannot > be done in O(n) time. Correct me if I am wrong!! Nevertheless, the overall > time complexity remains O(n*log(n)), as you pointed out. > > > On Tue, Jun 28, 2011 at 5:59 PM, Shachindra A C <sachindr...@gmail.com>wrote: > >> @Ankit >> Can you please explain the method to get the answer to the second subpart >> of your solution in O(n) time? >> >> My solution to solve the problem in O(n log(n)) time is as follows: >> >> Insert the nodes of the sorted array into a binary tree. Then start with >> the first node. Subtract the value of the node from X. Then search for the >> result of the subtraction in the binary tree. This can be done in O(log n) >> time, giving O(nlogn) for the overall complexity of the second subproblem. >> >> Please explain your logic. >> >> >> On Tue, Jun 28, 2011 at 5:48 PM, Nitish Garg <nitishgarg1...@gmail.com>wrote: >> >>> Can you please explain how to solve the 2nd question? >>> >>> -- >>> 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/-/5C-1NnideVgJ. >>> >>> 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. >>> >> >> >> >> -- >> Regards, >> Shachindra A C >> >> > > > -- > Regards, > Shachindra A C > > -- > 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. > -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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.
