We consider comparison as the operation to be analyzed

The pseudocode contains a nested loop.

In each iteration in the inner loop, there are 2 operations.

The inner loop is a while loop for variable j and the number of iterations is i-1 in the worst case.

There are at most 2\times (1+2+\cdots+(n-1)) + 2(n-1)+1 operation.

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

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

c = c + 1

break

procedure intersection_cardinality(A, B)

for i = 0 to m-1 do

    for j = 0 to n-1 do

end of if

c = 0 

    end of for j

end of for i

if a_i = b_j then 

return c

3a+7=3b+7

Assume f(x)=y.

Assume that f(a)=f(b).

x = \frac{y-7}{3} exists

Consider two arbitrary real numbers a and b.

3x+7=y

f is injective

proof

Consider an arbitrary real number y.

f is surjective

a = b

QED

3a+7=3b+7

Assume f(x)=y.

Assume that f(a)=f(b).

x = \frac{y-7}{3} exists

Consider two arbitrary real numbers a and b.

3x+7=y

f is injective

proof

Consider an arbitrary real number y.

f is surjective

a = b

QED

Case (1): a=b. 

In this case, we let c = lb-a and we will first derive the upper bound of c.

Since l=f(x,0)=x^2, k=x exists.

Case (2): a\not=b. Without loss of generality, we consider a>b. 

Next, we derive the lower bound of c.

Simplifying the inequality above, we have a+b>lb and the upper bound of c is c < b.

Simplifying the equation above, we have l(bc+1)=b^2+c^2>0 so we find that f(b,c)=l and the lower bound of c is 0 \leq c.

Using the direct proof technique, we assume that l=f(a,b) \in Z^+.

When l=f(a,b) for a pair of positive integers a and b, there are two cases.

In this case, f(a,b)=f(a,a)=\frac{2a^2}{a^2+1}=l.

Repeating the steps from Step 11, we can find a sequence of positive integers a>b>c>\cdots > x>0 such that f(a,b)=f(b,c)=\cdots=f(x,0)=l.

The logic statement to be proved is a universally quantified implication.

Since a=lb-c, we have a^2+b^2 = lab+l = l^2b^2 -2lbc + c^2 + b^2= l^2b^2 -lbc + l.

proof

Since l=1=1^2, k=1 exists.

Since a>b and f(a,b)=l \in Z^+, we can derive a^2+ab > a^2+b^2 = lab + l > lab.

QED

To use the UG rule, we consider two arbitrary positive integers a and b.

Since 2a^2 < la^2 +l when l \geq 2, f(a,a)=l implies that a=l=1.

So P(k+1)≡TP(k+1)≡TP( k+1 ) \equiv T.

Define predicate P(n)P(n)P( n ) as the equation that square_sum( n ) =n∑i=1(i2)\displaystyle=\sum_{i=1}^n (i^2), where n∈Z+n \in Z^+.

Using the direct proof technique, we assume that P(k)≡TP( k ) \equiv T so square_sum(k)=k∑i=1(i2)\displaystyle = \sum_{i=1}^k (i^2).

For P(1)P( 1 ), the left-hand side (LHS) = square_sum(1) =1=1∑i=1(i2)==1= \displaystyle \sum_{i=1}^1 (i^2) = the right-hand side (RHS), so P(1)≡TP( 1 ) \equiv T.

Basis step: to prove that P(1)≡TP( 1 ) \equiv T.

proof

For P(k+1)P( k+1 ), the LHS = square_sum(k+1) = (k+1)2+(k+1)^2+ square_sum(k) =(k+1)2+k∑i=1(i2)=k+1∑i=1(i2)== \displaystyle (k+1)^2+ \sum_{i=1}^k (i^2) = \sum_{i=1}^{k+1} (i^2) = the RHS.

Inductive step: to prove that ∀k(P(k)→P(k+1))≡T\forall k ( P( k ) \to P( k+1 ) ) \equiv T.

To use the UG rule, we consider an arbitrary positive integer kk.

QED

end of the second if

end of the first if

if (n==0)

return 1

return (a*a)

if (n is even)

a = power_bin(b, n div 2)

return (b*a*a)