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?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ What are the hypothesis on $a$ and $b$? Are they integers? $\endgroup$ Commented Jan 24, 2024 at 8:50

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.