Question

I need an algorithm that takes 2 sequences of numbers say A and B, both of size n, and takes one number call it x. Algorithm should determine if x \in {a_i + y_j | 1 <= i, j <= n}. It must have a universal hashing families, and complete in O(n) time.

My idea is that: summing up elements of A and B, and hashing the results, then placing them in hash table. I can then look up x in O(1) time by hashing it and looking up its hash value.

Any help would be really appreciated.

Answer 1

tough one, been a while since I've done algorithms. will bookmark this question and have a look in the morning.

Answer 2

hmm yea seems tough. an obvious brute force approach would be O(n^2) but doesn't quite fit the bill. are the sequences in sorted order by chance?

Answer 3

I would imagine if it says sequence that they do have some order, by the definition of a sequence...but doesn't specify. Does it matter if sorted?

Answer 4

Summing up elements of A and B would be O(n^2) time.

If they're sorted, you could start one pointer at the end of A, and one pointer at the beginning of B. Sum the two values pointed at. If it's bigger than x, decrease the A pointer. If it's less than x, increase the B pointer. If it's equal to x return true. If you reach the end of either list, return false.

It assumes the lists are sorted. It doesn't use universal hashing families. It is O(n).

If you could use hashing to somehow effectively sort the lists in O(n) time then you could use this algorithm on the sorted lists.

Answer 5

Summing up elements of A and B takes O(n^2) time? why?
Say
\[A = \{a_1, a_2, a_3, ..., a_n\}\ and\ B = \{b_1, b_2, b_3, ... , b_n\}\]
\[A + B = \{a_1 + b_1, a_2 + b_2, a_3 + b_3, ... , a_n + b_n\}\]
\[A + B \in O(n)\]

Answer 6

That will only give sums of elements in the same place in both lists. What if x was A[3] + B[11]? You would not generate that sum. Here's some python for generating all the sums:

for a in A: # O(n)
for b in B: # O(n)
total = a + b # O(1)

Total: O(n)*O(n)*O(1) = O(n^2)

Answer 7

True. Didn't think of that.

Isn't expected time 0(n) = average case running time?

Not sure its the worst-case analysis. Its the expected running time for a good universal hash function would be calculated by finding the expected value of collisions (different keys mapping to the same slot in the hash table).

So I guess: \[E[\#\ of\ collisions] \le O(n)\]

Answer 8

for every number in A, do the binary search for the number (x - A[i]) in sequence B . Binary search is log(n) and for n elements the algorithm will take n * log(n)

Answer 9

That would be O(n log n), which isn't O(n). And it assumes B is sorted.

But you could add all the elements from B to a hash table, then lookup would be constant time, so the overall time would be O(n). And neither A nor B would need to be sorted. AND it would use hashing. I think that's the answer.