1
$\begingroup$

Given an array with the size of $n$ of integer numbers. Our goal will be to analyze the expected running time of an algorithm that uses a hash table to find (if exists) a pair $(a,b)$ subject to $2<|a-b|<5$.

The answer is $O(n)$ but I have no idea to convince myself. Some thoughts that come to my mind are as follows: consider $a$ to find a $b$ in the hash table maybe I have a cost $1+2+\dots+n$ so for each $a$ the average cost will be $O(n^2)$. But the answer is $O(n)$. Anyone can correct my mistake?

$\endgroup$
1
  • 2
    $\begingroup$ What are the hypothesis on $a$ and $b$? Are they integers? $\endgroup$
    – SilvioM
    Jan 24 at 8:50

1 Answer 1

3
$\begingroup$

If all items in the hash table are integers, then the difference between a and b is 3 or 4. You need an iterator that iterates through all elements of the hash table in O(n) to find all possible values of b in random order; most hash table implementations will provide this. Then for each b you check whether b-3 or b-4 is in the hash table. That's O(n)

If the items in the hash table are real numbers, then the only way is to extract all values, sort them and iterate through the sorted array to find all pairs. Note that the number of pairs (a, b) can be O(n^2), for example if all values are between 1 and 2. The time is O (n log n + m), where m is the number of pairs (a, b). n log n is for sorting the values.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.