# Showing that algorithm has STOP property and finding its computational complexity function

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.

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