Question

Consider the following algorithm for computing integer powers:

Procedure power(integer x, integer n)  
    power := 1  
    for i := 1 to n  
        power := power * x
    return power

Can we say that the loop invariant is $power \leq x^n$ ?
Before the loop $power$ is initialized to $1$ so its equal to $1 \leq x^n$.

How do we prove maintenance of the invariant?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top