yeah, you're right. thank you and is it the optimal solution about this question?
On Thu, Dec 2, 2010 at 1:08 AM, Dave <dave_and_da...@juno.com> wrote: > @Fenghuang: No. You don't have to search for b for every a, or more > precisely, you don't have to search for a j for every i. Something > like this should work for step 3: > > i = 0 > j = k-1 > repeat while i <= j > if asq[i] + asq[j] < asq[k] then i = i+1 > else if asq[i] + asq[j] > asq[k] then j = j-1 > else break > end repeat > if i <= j then you have found an i, j, and k satisfying the desired > relationship; > otherwise, no such i and j exist for this k. > > This loop is O(n). Surround this with a loop over k and precede that > loop with a sort to get Senthilnathan's algorithm. So, as he says, the > whole task is O(n log n + n^2) = O(n^2). > > Dave > > On Dec 1, 10:11 am, fenghuang <fenghaungyuyi...@gmail.com> wrote: > > 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> > <algogeeks%2bunsubscr...@googlegroups.com> > > > . > > > For more options, visit this group at > > >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - > > > > - Show quoted text - > > -- > 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.
