On 2/14/07, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:
>
>
> Hello,
>
> There is a problem in the algorithm book I'm trying to digest, that
> I'd like to discuss a bit. So, first thing first, let me state the
> problem :
>
> ==
> Describe a O( n*lg(n) ) algorithm that, given a set of integers S a
Looks like the analysis sucked.
The answer is as follows:
Sort array (using merge sort) => n*log(n) complexity
for(i=0;a[i] n complexity
{
if(binary_search for value (x-a[i]) in the range i+1,n =>log(n) complexity
}
So sorting = n*log(n)
for loop and search = n*log(n)
Which gives overall comp
On 2/14/07, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:
>
>
> Hello,
>
> There is a problem in the algorithm book I'm trying to digest, that
> I'd like to discuss a bit. So, first thing first, let me state the
> problem :
> find(A, x)
> sort(A)
> i = 1
j = n
while (A[i]+A[j] != x)
>
