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 and
another integer x, determines, weather or not, there exist two
elements n1,n2 in S so that n1 + n2 = x.
==
OK, so now, regrading the questions - I've made an attempt to write an
algorithm as follows :
==
find(A, x)
sort(A)
i = 1
while (A[i] < x)
n2 = x - A[i]
if (binary_search(A, n2) == SUCCESS)
return EXISTS
i = i + 1
return not EXISTS
==
So, presuming the algorithm is correct, I get the following time
complexity :
sorting : n*lg(n)
loop : n - 1
binary_search n*lg(n) * (n-1)
summing these things up we have :
n*lg(n) + n - 1 + n*lg(n)*(n-1)
n*lg(n) + n - 1 + n*lg(n)*n - n*lg(n)
cancelling out n*lg(n) and ignoring the linear terms, we have :
n*lg(n)*n, which is :
n^2*lg(n)
So, either my algorithm sucks, or, my analysis skills suck, or, most
probbably, both suck :-)
Anyway, can someone check that algorithm and reasoning, correct any
mistakes, or supply a better algorotihm for the task?
Thanks.
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
