@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>
> > .
> > 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.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
