Brute Force Algorithms

What is brute force algorithm?

It is a problem solving technique that works every possible solution until the correct one is found.

Examples of brute force

1. Computing a^n where a > 0 and n is any positive integer

2. Computing n!

3. Multiplying two matrix

Advantages of brute force:

1. It is very simple implement and can find any answer as long as it exists

2. It is can work with smaller problems

3. It saves development time

Disadvantages of brute force:

1. Some brute force algorithms are very slow

2. It is not as constructive as other techniques

Brute Force Algorithms:

1. Selection sort

2. Bubble sort

3. Sequential search

4. Brute force string matching

5. Exhaustive search

Selection sort

It orders a list by repeatedly finding the smallest number in the unsorted list and swapping it so its the first in the sort list.

Steps for selection sort

1. Find the smallest value

2. Swap it with the first value

3. Repeat the steps for the rest of the list, starting from the second position

Selection sort efficiency

0(n²) for all cases

Bubble Sort

It repeatedly swaps adjacent numbers or elements until the list is sorted. During the first pass the largest number should last in the list.

Steps for bubble sort

1. Look at the two adjacent elements.

2. Swap so that the first one is the smallest. If the smallest between the two is already first then compare the next adjacent element to the largest element of your first two

3. Continue until the largest number in the list is in the last position. This is the first pass

4. Continue until the list is sorted.

Bubble sort efficiency

0(n²) for all cases

Sequential Search / Linear Search

This searches for a key in the list to find a match. It searches in the same order it appears

Linear Search Efficiency

Best case: 0(1)

Average & Worst Case : 0(n)

Brute Force String Matching

This checks every character from the text to match the pattern

Steps for brute force string matching

1. Check for a match between the first letter of the pattern and the first letter of the text

2. If it doesn’t match we go to the next character of the text, if the match is in the character from the pattern then compare the next character in the pattern to the text

Brute Force String Matching

Best Case & Average case: 0(n)

Worst case: 0(nm) n-length of text, m-length of pattern

Exhaustive Search

A method used for complex puzzles where the number of possibles grows massively.

Exhaustive Search Efficicey

All cases are 0(n!)