@sagar : oops ! No need of sorting. Thank you for pointing out :) On Tue, Jun 28, 2011 at 6:41 PM, sagar pareek <[email protected]> wrote:
> @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 <[email protected]>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 <[email protected]>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 >>> <[email protected]>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 [email protected]. >>>> To unsubscribe from this group, send email to >>>> [email protected]. >>>> 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
