Loop Invariant:
Initialization:
1. The loop invariant states that after the 0th iteration...
2. Loop Invariant at alpha = 0
3. Before the first iteration ...
4. explanation of all the code before the loop
5. Thus the invariant is true after the 0th iteration (before first)
Maintenance:
1. Assume that the loop invariant is true after the (alpha - 1)th iteration. I will prove that after the (alpha)th iteration...
2. State loop invariant at alpha = alpha
3. On the (alpha)th iteration...
4. explanation of all the code within the body of the loop (might need to show mathematical logic)
5. As we can see, the invariant holds true after the (alpha)th iteration, thus proving maintenance.
Big-Theta, Big-Oh, Big-Omega
For the following definitions, recall that N+ is
...