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

  • 1
    $\begingroup$ By "STOP property" you mean the algorithm terminates? $\endgroup$ – dkaeae Dec 3 '18 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 '18 at 10:30
  • $\begingroup$ Yes. It means that the number of steps is finite so it will terminate as you have written. $\endgroup$ – James Smith Dec 3 '18 at 10:31
  • $\begingroup$ It is supposed to be $(a+1)$ != $b$ (is not equal) $\endgroup$ – James Smith Dec 3 '18 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 '18 at 11:33

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.


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.