Brute Force¹1. Brute-force approaches rarely employ advanced techniques, relying instead on raw computational power to enumerate or traverse all possibilities.: Straightforward approach, usually based directly on problem’s statement and definitions of the concepts involved.

Examples of Brute-force:

1. Computing a^n
2. n!
3. Multiplying two matrices
4. Searching for a key in a list

Brute-Force Sorting Algorithm: Selection Sort

Selection Sort: Iterate over array. Every iteration, swap the smallest element with the element in A[i]²2. i starts at 0.. Each iteration, increment i. Go until you’ve covered the whole array³3. 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.

Analysis — Time: The basic operation is the comparison A[j] < A[min], and number of times it executes depends on array size. Space: O(1).

Note — Q: Why not min <- j or swap?

• A: Because both of those execute less often.

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

Thus, it is O(n^2).

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])
// Sorts a given array by bubble 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-2 do
    for j \leftarrow 0 to n-2-i do
        if A[j+1] \lt A[j] swap (A[j], A[j+1])

Analysis — Basic operation is the comparison. Time complexity is \Theta(n^2) across all cases. Space complexity is O(1). The worst-case number of swaps is \frac{n(n-1)}{2}.

\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.
• text: longer string of n chars to search in

Steps:

1. Align pattern at beginning of text.
2. Moving from left \to 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 — Time complexity varies:

• Best Case: The pattern is at the start of the text. O(m) comparisons.
• Worst Case: The pattern does not exist, and we fail on the last character every time. Outer loop runs n - m + 1 times. Within the loop, we do m 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).