Crowdly

Judging whether the following statement is True or False:

6|36 | 3

100%

Given a positive integer mmm and two integers aa and bb, a≡ba \equiv b (mod mm) if and only if m|(a−b)m | (a-b).

100%

Judging whether the following statement is True or False:

3|63|63 | 6

Finding the remainder: -44 mod 9

Finding the remainder: 88 mod 19

Given a positive integer mmm and two integers aaa and bbb, a≢ba≢ba \not\equiv b (mod mmm) if and only if aaa mod m≠bm≠bm \not=b mod mmm.

100%

Finding the quotient: -84 div 6

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

Matching each statement with the correct sequence in a formal proof.

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

Given the following algorithm, matching each statement to the correct sequence for complexity analysis.

procedure TailSums(A): A is a list of n integers

1 for i = 0 to n-2 do

2 j = i + 1

3 while (j < n) do

4 A[i] = A[i] + A[j]

5 j = j + 1

6 end while

7 end for

8 return A

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 )