CODEWITHSUNDEEP
c++algorithm
Walter White
Walter White

Reputation: 51

Algorithm of finding matching elements

We are given table_1: 6 3 2 5 2, table_2: 7 4 1 6 8, table_3:15,14,5,4,9. The number of elements in table_1 is equal to the number of elements in table_2. How to find FAST if there exist such elements in table_1, table_2 that for particular element from table_3: table_3[i]=table_1[k]+table_2[p].

Example: 9=table_3[4]=table_1[1]+table_2[3];

I tried to sorting and binary_search algorithm so solve this problem :/ but it gives still too slow solution.

Upvotes: 0

Views: 404

Answers (1)

P. Hinker
P. Hinker

Reputation: 297

You say that O(nlogn) is too slow. Do you mean that your particular implementation of some O(nlogn) solution was too slow or any growth of O(nlogn) is going to be too slow? If that latter is the case then you are, as my son would put it, boned.

Let's look at this from a data structures and algorithm analysis standpoint. If you allow table_1 and table_2 to remain unordered then you will need to make n^2 pairwise comparisons. Therefore, table_1 and table_2 must be submitted to some sort of ordering process.

There is no chance you will be able to order the two tables in less than linear time simply because each element will need to be subjected to at least one access. There are some sorting methods whose best time complexity is linear but I assume you need a general solution which means you have no guarantees on the state of the data before you start. I think sorting is a loser's bet anyway since you'll pay the O(nlogn) sort cost only to find you need, on average, n/2 average case compares to check the pairwise summations.

Now, you could create minheaps in linear time but table_3 is O(n) in size as are table_1 and table_2. You still lose since you will still need to do n * n/2 average comparisons to check the values of table_3 against the combination of pairs from table_1 and table_2.

What are the time constraints on this solution? 1 ms, 1 sec? Is there some structure or pre-knowledge about the data that can allow for a solution that takes advantage of the data? If not, I do not see a solution.

Upvotes: 2

Related Questions