@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.
