Brute Force: Straightforward approach, usually based directly on problem’s statement and definitions of the concepts involved.

Brute-Force Sorting Algorithm: Selection Sort

Selection Sort: Iterate over array. Every iteration, swap the smallest element with the element in A[i] (4i4 starts at 0). Each iteration, increment i. Go until you’ve covered the whole array (up to n-2, because at that point you have nothing left to swap)

ALGORITHM SelectionSort(A[0..n-1])
    // Sorts a given array by selection sort
    // Input: An array A[0..n-1] of orderable elements
    // Output: Array A[0..n-1] sorted in ascending order
    for i \leftarrow 0 to n \text{$-$} 2 do
        min \leftarrow i
        for j \leftarrow i \text{$+$} 1 to n \text{$-$} 1 do
            if A[j] \lt A[min] min \leftarrow j
        swap A[i] and A[min]

Analysis is straightforward.

Time: The basic operation is the comparison A[j] < A[min], and number of times it executes depends on array size:

Q: Why not min <- j or swap?

• A: Because both of those execute less often.

C(n) = \sum_{i=0}^{n-2} \sum_{j=i+1}^{n-1} 1 \\ \text{apply Counting summation} \\ = \sum_{i=0}^{n-2} [ (n-1) - (i+1) + 1 ] \\ = \sum_{i=0}^{n-2} ( n - 1 - i ) \\ \text{apply Arithmetic progression} \\ = \frac{(n-1)n}{2}

Thus, it is O(n^2).

Space: O(n)

Bubble Sort

Compare adjacent elements of the list and exchange them if they’re out of order.

• Doing repeated passes bubbles up the large values

ALGORITHM BubbleSort(A[0..n-1])
for i \leftarrow 0 to n-2 do
    for j \leftarrow 0 to n-2-i do
        if A[j+1] \lt A[j] swap (A[j], A[j+1])

Basic operation is the comparison

\begin{aligned} C(n) &= \sum_{i=0}^{n-2} \sum_{j=0}^{n-2-i} 1 \\ &= \sum_{i=0}^{n-2} \left[ (n-2-i) - 0 + 1 \right] \\ &= \sum_{i=0}^{n-2} (n-1-i) \\ &= \frac{(n-1)n}{2} \in \Theta(n^2) \end{aligned}

Brute-Force String Matching

We want to find if some pattern (substring) is in a text (string).

• pattern: String of m chars to search for.
• test: longer string of n chars to search in

Steps:

1. Align pattern at beginning of text.
2. Moving from left right, compare each character of the pattern to the pattern until:
   • Success (all chars found), or
   • Failure (mismatch found)
3. While pattern isn’t found and text isn’t exhausted, move pattern to the right by one and goto step 2.

Pseudocode:

ALGORITHM BruteForceStringMatch(T[0..n-1], P[0..m-1])
    // Implements brute-force string matching
    // Input: Array T representing text, array p representing pattern
    // Output: Index of first char of matching substring, or -1
    for i \leftarrow 0 to n \text{$-$} m do
        j \leftarrow 0
        while j<m and P[j]=T[i+j] do
            j \leftarrow j \text{$+$} 1
        if j = m return i
    return -1

Analysis:

• Best Case: The pattern is at the start of the text..
• Worst Case: The pattern does not exist
  • Outer loop runs from n - m + 1 times (i \leftarrow 0 to n - m)
    • Within the loop, we do n comparisons.
      • Thus, it is in the O(nm) class.
• Average Case: The math is very complicated, but we at least know the lower and upper bound.
  • (Though, the math has been done and shows that it’s O(n) on random texts)