Brute Force Algorithm (accessible v.)

Brute Force Algorithm — This algorithm tries every possible combination of solutions to a problem, making it highly inefficient for problems with large input sizes. A brute force algorithm is a simple and exhaustive method of solving a problem by checking all possible solutions, even those that are not likely to be correct. It works by trying every possible combination of solutions to a problem until a solution is found. While this approach can be straightforward to implement, it can also be prolonged and inefficient, particularly for large input sizes.

Figure: Password cracked using brute force algorithm(image Mehmet Akif CIFCI)

The time complexity of a brute force algorithm is often proportional to the input size, which means that as the size of the input increases, the algorithm's running time also increases. This can lead to long computation times and is not practical for problems with large input sizes. Despite their limitations, brute force algorithms are sometimes used for small or straightforward problems or when no other algorithm works. They are also helpful for verifying the correctness of different algorithms, as they provide a baseline for comparison.

In summary, brute force algorithms are simple and consistent but can be very slow and inefficient for problems with large input sizes. They are typically only used as a last resort, and other, more efficient algorithms are preferred whenever possible. Suppose you have a list of numbers and you want to find the pair of numbers in the list that adds up to a specific target value. One approach to solving this problem is to use a brute force algorithm:

1. For each pair of numbers in the list, check if they add up to the target value.

2. If a pair is found that adds up to the target value, return that pair.

3. If no pair is found, return an error message indicating that no such pair exists.

def find_pattering(numbers,targets):
    for i in range(len(numbers)):
        for j in range(i+1, len(numbers)):
            if numbers[i] + numbers[j] == targets:
                return (numbers[i], numbers[j])
    return "No such pair exists"

numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12,13,23,24,25]
targets = 5
find_pattering(numbers, targets)

In this implementation, the algorithm checks every possible pair of numbers in the list, which has a time complexity of O(n²), where n is the size of the input list. This makes the algorithm inefficient for large input sizes, but it is guaranteed to find a solution if one exists.

Overall, this is an example of a simple brute-force algorithm that can be used to solve a specific problem, but it can be slow for more significant inputs.

To calculate the time complexity of the brute force algorithm I provided as an example, we can analyze the number of operations it performs as a function of the input size. In implementing the algorithm, we have two nested loops that iterate over all possible pairs of numbers in the input list. The outer loop iterates over each list element, and the inner loop iterates over all remaining elements after the current element. This means that the inner loop performs n — i — 1 iterations for each iteration of the outer loop, where n is the size of the input list, and i is the index of the current element in the outer loop. The total number of iterations performed by the algorithm is, therefore:

(n-1) + (n-2) + (n-3) + … + 1 = n*(n-1)/2

This corresponds to a time complexity of O(n²), as the number of operations performed by the algorithm grows quadratically with the input size.

In the worst case, where no pair of numbers in the input list adds up to the target value, the algorithm will perform the maximum number of iterations, n*(n-1)/2. However, in the best case, where the first pair of numbers in the list adds up to the target value, the algorithm will perform only one iteration.