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.

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ By "STOP property" you mean the algorithm terminates? $\endgroup$ Commented 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$ Commented 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$ Commented Dec 3, 2018 at 10:31
  • $\begingroup$ It is supposed to be $(a+1)$ != $b$ (is not equal) $\endgroup$ Commented 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$ Commented Dec 3, 2018 at 11:33

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.