0
$\begingroup$

I have designed an algorithm (up to making a pseudocode) that accepts a sorted array as input and finds in $O(n)$ time if there's a pair of elements (integers) in the array that have a sum zero.

What my algorithm basically does is:

  1. set index $i$ = 0
  2. set index $j$ = length(array) - 1
  3. while $i<j$ : if $a[i]+a[j]=0$ then it returns the pair, if $a[i]+a[j]<0$ it does $i++$ and if $a[i]+a[j]>0$ it does $j--$.
  4. if at some point $i=j$ it stops and returns that the pair was not found.

I read that when making an algorithm you need to prove its correctness, but the methods that I've read don't seem fitting to me. I can't think how to use induction - for example - past the "assume it works for $n=m$" because I feel like I'd be explaining how the algorithm works again.

Can someone indicate how I can prove the correctness?

$\endgroup$
4
  • 1
    $\begingroup$ Merge sort uses $\mathcal{O}(n\log n)$ time, not $\mathcal{O}(\log n)$ time. $\endgroup$
    – Nathaniel
    Nov 29, 2022 at 19:11
  • $\begingroup$ @Nathaniel Yes, my bad, the sorting shouldn't be taken into account for the complexity, I'll edit my question so it is correct. $\endgroup$
    – Tita
    Nov 29, 2022 at 19:15
  • 1
    $\begingroup$ I think there is a confusion in the third item: you write "if $i+j = 0$", but it should be "if $a[i] + a[j] = 0$", and same thing for the other comparisons. $\endgroup$
    – Nathaniel
    Nov 29, 2022 at 19:26
  • $\begingroup$ @Nathaniel You are absolutely right. I'm sorry that's what in my pseudocode as well, it's just late, I've been working all day and made mistakes. Thanks for bringing them up. $\endgroup$
    – Tita
    Nov 29, 2022 at 19:28

1 Answer 1

-1
$\begingroup$

You can prove this property using a loop invariant. Naming the array $a$ and $n = |a|$, consider the following property $(P)$:

There exist $(k,\ell)\in \{0, …, n-1\}, k\neq \ell$, such that $a[k] + a[\ell] = 0$ if and only if There exist $(k,\ell)\in \{i, …, j\}, k\neq \ell$, such that $a[k] + a[\ell] = 0$

Meaning that the two indices you are searching for are necessarily between $i$ and $j$ (included).

Then, the property $(P)$ is a loop invariant of your algorithm:

  • it is trivially true before the loop;
  • it stays true at each step of the loop, considering all three cases (proof left to you).

Now, you can use this loop invariant to prove the correctness of your algorithm.

$\endgroup$
7
  • $\begingroup$ Thank you for your reply! I've never used the loop invariant method, so I wasn't familiar with it. :) $\endgroup$
    – Tita
    Nov 29, 2022 at 19:37
  • 1
    $\begingroup$ It is one of the most elementary method for proof: induction for recursion, loop invariant for loops. $\endgroup$
    – Nathaniel
    Nov 29, 2022 at 19:39
  • $\begingroup$ I have probably come across it a CS class, but we rarely focused on proofs which is why it was weird to me that I read we have to prove algorithms on top of explaining how they work, even if logically they make sense. Thanks for the boost, I'll definitely read more on algo proofs moving forward! $\endgroup$
    – Tita
    Nov 29, 2022 at 20:00
  • 1
    $\begingroup$ There is an important ingredient missing: proving that the algorithm does terminate. $\endgroup$
    – user16034
    Nov 30, 2022 at 10:39
  • $\begingroup$ @YvesDaoust you are right, but since OP said they already had computed the complexity, I assumed termination was not the difficult part. $\endgroup$
    – Nathaniel
    Nov 30, 2022 at 10:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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