1
$\begingroup$

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).

$\endgroup$
  • 1
    $\begingroup$ Show what you have done so far, then we will be able to help you=) $\endgroup$ – TZakrevskiy Jan 25 '17 at 18:08
  • $\begingroup$ Start with i = j = 0. Check the difference. In one case, you increment i, in the other case you increment j. Take advantage of the fact that the list starts out in ascending order. $\endgroup$ – DanielV Jan 25 '17 at 18:11
  • $\begingroup$ You will find "saddleback search" a useful term to "google". $\endgroup$ – hardmath Jan 26 '17 at 18:46
1
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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