1
$\begingroup$

The task is to show that given algorithm has STOP property and to find its computational complexity function.

$\alpha:$ $n \ge 0$

void fun(int n) { 
    a=0;b=n+1; 
    while ((a + 1) != b) {
        p = (a + b)/2;
        if (p ∗ p > n) 
            b = p; 
        else a = p; 
    }
}

I have already proven its partial correctness as it was also part of the task, however I do have problem with these things that I have mentioned above.

I think it can be easily seen that it is gonna stop as 'a' is getting bigger and bigger, but I don't really know how to notate or show it in more mathematical way.

Thanks for your help.

$\endgroup$
8
  • 1
    $\begingroup$ By "STOP property" you mean the algorithm terminates? $\endgroup$
    – dkaeae
    Dec 3, 2018 at 10:25
  • $\begingroup$ Also, is (a + 1)! = b supposed to be (a + 1) != b or do you really mean the factorial $(a + 1)!$ of $a + 1$? $\endgroup$
    – dkaeae
    Dec 3, 2018 at 10:30
  • $\begingroup$ Yes. It means that the number of steps is finite so it will terminate as you have written. $\endgroup$ Dec 3, 2018 at 10:31
  • $\begingroup$ It is supposed to be $(a+1)$ != $b$ (is not equal) $\endgroup$ Dec 3, 2018 at 10:32
  • 1
    $\begingroup$ You should be able to prove that, if $b-a > 1$, then after one iteration the difference $b-a$ decreased. This is because one of those endpoints was moved to $p$ which lies in the middle. So, eventually $b-a=1$ (since the difference is always positive, according to your invariant) and the loop stops. $\endgroup$
    – chi
    Dec 3, 2018 at 11:33

1 Answer 1

1
$\begingroup$

You have already proven $a < b$. Let $g$ be the gap between $a$ and $b$, so $b - a$.

  1. Show that the algorithm terminates when $g = 1$.

  2. Show that when $g > 1$ we have as postcondition that the new $g' \leq \lceil g/2 \rceil$ in the loop body, and thus $g' < g$.

  3. Show that it's impossible to skip $g = 1$, and thus the algorithm must terminate.

$\endgroup$

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.