CLRS chapter 2

2.1

In this section:

• Sorting algorithm
  • Insertion sort
• Searching algorithm
• Pseudocode
• Loop invariant

2.1-2

Predicate: the variable sum contains the algebraic sum of all elements of A[1:i - 1] at the beginning of each iteration of the for loop.

• Initialisation — we initially have A[0], sum = 0, outside of the array, for a sub-array of 0 elements. The sum thus is 0.
• Maintenance — assume the invariant holds true for some iteration $k\in [1,n)$. Then, for $k+1$. Before the loop, we have the sum of all elements from $1:k$. We add A[k + 1] to sum, effectively summing everything.
• Termination — our loop terminates after we finish A[n], i.e., $i=n+1$.

2.1-4

LINEAR-SEARCH (A, s):
	for i = 1 to n:
		if A[i] == s: return i
	return -1

Predicate: the sub-array A[0:i - 1] does not have the search element s at the beginning of an iteration i of the for loop OR i holds the first occurrence of s in A.

• Initialisation — we initially have an empty array, so $s\notin \varnothing$.
• Maintenance — assume the invariant holds true for some iteration $k\in [1,n)$. Then, for $k+1$. Before the loop, we have a sub-array A[0:k] that doesn’t contain s.
  • We have two cases: one where it is and one where it isn’t. If it isn’t, then the predicate still holds true for the next iteration.
  • If it is, the loop immediately terminates and the second statement is true.
• Termination — the loop either terminates if $i=n+1$ or if the search element is found.

2.3

2.3-4

$$T(n)=\{\begin{array}{ll}2& n=2\\ 2T(n/2)+n& n>2\end{array}$$

For the base case, $n=2$. Then, $T(2)=2=2{\log }_{2}2$. So we’re good for now.

For the case where $n=k$, where $k\in \mathbb{Z}$ and is an exact power of 2, we have:

$$T(k)=2T(k/2)+k$$

We assume this holds true. Then, for $n=2k$, we have:

$$T(2k)=2T(k)+2k$$