Test by Bikram | Mock GATE | Test 4 | Question: 4

Question

Consider a sorted array of $p$ numbers. What would be the time complexity of the best known algorithm to find a pair $x$ and $y$ such that $\left | x-y \right |$ $=$ $m$ (where $m$ is a positive integer) ?

• A.   $O$$\left ( \log p \right )$
• B.   $O$$\left ( p \right )$ but not in $O$$\left ( \log p \right )$
• C.   $O$$\left ( p^{2} \right )$
• D.   $O$$\left ( p\log p \right )$but not in $O$$\left ( p \right )$

Answer 1

Given array is sorted. Let two pointers $i$ and $j$, both be pointing to the first element.
If the difference of elements $arr\left [ i \right ]$ and $arr\left [j \right ] > m$, increment $i$.
If the difference of elements $arr\left [ i \right ]$ and $arr\left [ j \right ]$ is $< m$, increment $j$.
Otherwise, we found the exact difference $m$ at indices $i$  and $j$.

This procedure will take $O$$\left ( p \right )$time but not $O$$\left ( \log p \right )$.

option $B$