Using the UG rule, we consider an arbitrary integer nn.

n2>n>1n^2 > n > 1

To prove ∀n((n>k)→(f(n)<Cn2))\forall n ((n > k) \to (f( n ) < C n^2)), where n∈Zn \in \mathbb{Z}

Using the direct proof, we assume that n>k=1n > k = 1.

To prove f(n)f( n ) is O(n2)O ( n^2 ), we use the constructive proof technique, and let k=1k=1 and C=20C=20.

We have shown that there exist kk and CC such that ∀n((n>k)→(f(n)<Cn2))\forall n (( n > k) \to (f( n ) < C n^2)), where n∈Zn \in \mathbb{Z}.

f(n)=5n2+6n+7f( n ) = 5n^2+6n+7 is O(n2)O( n^2 )

proof

f(n)=5n2+6n+7<5n2+6n2+7n2=18n2<20n2f( n ) = 5n^2+6n+7 < 5n^2+6n^2+7n^2 = 18n^2 < 20 n^2

QED

We consider comparison as the operation to be analyzed

The pseudocode contains a nested loop.

There are (1+2+⋯+(n−1))+2(n−1)+1(1+2+\cdots+(n-1)) + 2(n-1)+1 operation.

In each iteration in the inner loop, there is 1 operation.

The inner loop is a while loop for variable jj and the number of iterations is n−i−1n-i-1.

The outer loop is a for loop for variable ii and the number of iterations is n−1n-1.

The complexity of this algorithm is O(n2)O( n^2 )