Finding pairs $a \in A$, $b \in B$ where $a \ge 3b$ in linear time
If you need to list all output pairs, as you say, then the problem can't be solved in any less than quadratic time, for the reason that the output may be of quadratic size. Imagine that $A$ and $B$ are both half the input (say, both length $n$), and
\begin{align*}
A &amp;= [3n + 1, 3n+2, 3n+3, \ldots, 4n-1, 4n] \\
B &amp;= [1, 2, 3, \ldots, n]
\end{align*}

Then the output to your problem is all pairs of an element in $A$ and an element in $B$, and there are $n^2$ such pairs.

Probably there is an additional fact you haven't mentioned, that you don't have to produce all pairs, but you just have to produce a more compact representation of the output (e.g. for each $a \in A$, you only need to produce the maximal $b \in B$ such that $a \ge 3b$).

A hint for this altered version, where you only need the maximal $(a,b)$ pairs:

Imagine you are iterating through both $A$ and $B$ at once, instead of just iterating through $A$ or $B$ separately. So, you are keeping two pointers, one into $A$ and one into $B$. Suppose you have found the maximal pair for $a$, so you know $(a, b)$, and the next element in $A$ after $a$ is $a'$. What should you do?