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 < [email protected]> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > 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 [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.
