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 -~----------~----~----~----~------~----~------~--~---