TITLE: Algorithm to find difference between two array members
QUESTION [1 upvotes]: I have a question concerning algorithms and time complexity(analysis).So I have a field A,which is sorted and has natural numbers where n is >=2(ascending order).How would you write an algorithm which has 2 indices,so that N[i] - N[j]=1750,if those two indices exist.Wenn those two don't exist,then the Algorithm needs to return 0.The Time Complexity should be T(n)=O(n).I keep trying but I fail,because everytime I get O(n^2).

REPLY [1 votes]: HINT
Have a pointer $p = N[0]$ and $q = N[1]$. Then shift $p$ if you have $q-p> 1750$ and $q$ if $q-p < 1750$.
{"set_name": "stack_exchange", "score": 1, "question_id": 2113720}