clrs - Can we prove correctness of algorithms using loop invariants in which we prove that it is true after the first iteration rather than before? -

clrs - Can we prove correctness of algorithms using loop invariants in which we prove that it is true after the first iteration rather than before? -

clrs says

we must show 3 things loop invariant:

initialization: true prior first iteration of loop. maintenance: if true before iteration of loop, remains true before next iteration. termination: when loop terminates, invariant gives useful property helps show algorithm correct.

my question can edit steps , create them these instead:

initialization: true after first iteration of loop. maintenance: if true after iteration of loop, remains true after next iteration. termination: when loop terminates, invariant gives useful property helps show algorithm correct.

explanation: utilize principle of mathematical induction prove correctness. using "initialization" prove property holds after 1st iteration. using "maintenance" can show property holds iterations since "initialization" , "maintenance" create chain. , hence property holds after lastly iteration too.

example:

randomize-in-place(a) 1 n ← length[a] 2 ← n 3 swap a[i] ↔ a[random(i, n)]

for algorithm, there proof given in textbook using standard procedure (i didn't include here since long).

my suggestion:

loop invariant: after ith iteration of loop of lines 2-3, each possible (i)-permutation, subarray a[1 .. i] contains (i)-permutation probability (n - i)!/n!. initialization: after 1st iteration a[1] contains permutation probability (n-1)!/n!=1/n true. maintenance: allow true after (i-1)th iteration. after (i)th iteration, a[1...i] contains permutation probability [(n-i+1)!/n!]*[1/(n-i+1)]=(n-i)!/n! want. termination: @ termination, = n, , have subarray a[1 .. n] given n-permutation probability (n - n)!/n! = 1/n!. thus, randomize-in-place produces uniform random permutation.

is explanation logically sound?

any help appreciated. thanks.

apart fact, have create additional step, covers loop never running @ all, can of course of study prove invariant true after first iteration instead of proving true before first iteration.

however uncertainty create much sense

first, stated have special case (what happens if loop isn't executed @ all) results in proof, similar initialization, wanted skip in first place secondly, proof invariant true after first iteration, similar maintanance proof, write 2 similar proofs, skip initialization, quite easy proof.

analogy

although not straight related, question sounds lot trying optimize next (pseudo)code:

int product(int[] values) product = 1 = 0 values.size - 1 product *= values[i] homecoming product

to this:

int product(int[] values) product = values[0] // create code quicker, start first item = 1 values.size - 1 // start loop @ sec item product *= values[i] homecoming product

just, have include additional check, whether values array empty (which did not in above code)

algorithm clrs loop-invariant