Upper and lower bound of while loop

Question

I am stuck on a question in a past paper for an embedded software course.

The question asks the following:

Let n be the number of iterations of the while loop. Calculate an upper and lower bound on the value of n given that b <= bmax.

x=a
if x<1
then 
  x=1
end if
while x<b
  loop
    x=x+1
  end

I think that the upper bound would be: n<=bmax but I don't understand how to calculate a lower bound. Can anyone help?

Thanks

Answer 1

For the lower bound, you get that when a > 1. Then x starts at a instead of at 1, so you need fewer iterations to get from there to b.

If you start with x = a, and the last iteration happens when x = b (you fail the test), then you needed a total of b - a iterations. Since b <= bmax, the answer is:

lower bound : bmax - a
upper bound : bmax - 1

Note that if a >= bmax, the lower bound reduces to 0, as you cannot have fewer than 0 iterations.

Answer 2

Given only the information provided, the best you can do is the trivial lower bound - 0 iterations. This is because when a>=b, the loop won't execute at all.

As for the upper bound, you have an off by one error. Since x starts at a minimum of 1, you can have up to bmax-1 iterations, not bmax.

Answer 3

I think the question is: b is some b <= bmax. Now express the number of iterations n, in terms of bmax and a. The lower bound on n is trivial, 0, if a >= bmax; The upper bound on n is the case a < 1, which yields: n = bmax - 1.

Answer 4

upper bound: max(0,b-1) <= max(0,bmax-1)

lower bound: if (a<1) then max(0,b-1), else max(0,b-a)

The lower bound cannot be expressed with bmax instead of b, because we have b<=bmax, not bmax<=b. If we are not allowed to use b, then it is 0.