fibonacci(int n)
if n < 0
return 0;
else if n = 0
return 0;
else if n = 1
return 1;
else x = 1;
y = 0;
for i from 2 to n {
t = x;
x = x + y;
y = t;
}
}
return x;
I'm trying to find a loop invariant for the above algorithm, but am not sure where to start. I know that the invariant must hold true immediately before and after completion of the loop. How would I go about doing this?