1. Yes. Justification: Let c=1, n_0=1; then for all n >= n_0, we have n^2 <= c * n^3. You did not need to provide any justification or explanation; just "yes" was OK. 2. One suitable invariant is: (1) For every k such that 0 <= k < i, we have A[k] <= midpoint, and for every k such that i <= k < j, we have A[k] > midpoint. That's a little bit lengthy to write out. Here's another way to state the same invariant, but just slightly more concisely: (2) Every element in A[0..i-1] is <= midpoint, and every element in A[i..j-1] is > midpoint. As a matter of convention, the slice A[0..0] represents just a single element from A, and the slice A[0..-1] represents no elements (the empty set). With this convention, invariant (2) is equivalent to (1); (2) is just a slightly more concise way to state it. Another suitable invariant is (3) {A[k] : 0 <= k < i} = {origA[k] : 0 <= k < j and origA[k] <= midpoint} and {A[k] : i <= k < j} = {origA[k] : 0 <= k < j and origA[k] > midpoint} where origA[] denotes the original value of A[] when Partition was called. (3) is slightly stronger than invariants (1) or (2), because (3) also expresses the fact that the first j elements of A[] are a permutation of the first j elements of origA[]. This makes it easy to see that after Partition finishes executing, A[] contains a permutation of the elements of origA[]. If we used invariants (1) or (2), to prove Partition correct we'd need to make a separate argument why the final value of A[] is a permutation of the elements of origA[] (fortunately this is easy to see: it follows since the only modifications that Partition makes to the array A[] are a series of swaps, which always preserves the permutation property). In short, any of (1), (2), or (3) are acceptable. You did not need to provide any justification or explanation. The invariant (4) A[i] <= A[j] is indeed an invariant but it is not sufficient to prove correctness of the algorithm. After the last iteration of the loop, this invariant only relates two elements of A[]; it doesn't tell us anything about where the remaining elements are placed. So (4) won't do the job. Similarly, (5) i <= j is also an invariant, but it is not sufficient to prove correctness of Partition, either, because it doesn't promise anything about the order in which the elements of A[] appear. Some people wrote invariants stating that the elements of A[] (or portions of the elements of A[]) were sorted. This is not correct; the array A[] will usually not be sorted. For instance, if the midpoint value is 50, then after running Partition, a possible value for A[] might be {7,2,15,72,80,66,51}. Here the array is not sorted, but all values below 50 appear before any value larger than 50. When proving correctness, the trick is to come up with a property that is powerful enough to imply that the algorithm outputs the right answer; but that is also true in every iteration of the loop (and so is an invariant).