should it be O(n^2*lgn)? for each x in n, it's O(n), and for each a, it'sO(n), and searching b, it's O(lgn), so it's O(n*n*lgn),Thank You!
On Wed, Dec 1, 2010 at 11:02 PM, Senthilnathan Maadasamy < senthilnathan.maadas...@gmail.com> wrote: > Hi, > How about the following approach? > > Step 1: Replace each array element with its square - O(n) > > Step 2: Sort the array - O(n*log(n)) > > Step 3: For each element x in the array > Find two elements a, b in the array (if any) such that > a+b = x. > Since finding two such elements can be done in O(n) time in a > sorted array, the complexity of this step 3 is O(n^2). > > While reporting the output you can take the square root and print it out. > > Total complexity is O(n^2). > > > > -- > 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
