Find two closest points in a set of n points in a two-dimensional Cartesian plane.
Brute Force Solution:
Q: What is the basic operation?
A: Calculating the distance between two points.
e.g., suppose you want to find the distance between Point A and Point B.
d = \sqrt{ (x_a - x_b)^2 + (y_a - y_b)^2 }
The basic operation is the squaring and adding inside the square root, or effectively the Euclidean distance calculation.
Q: How many times does basic operation execute?
A:
We know it depends on the # of different pairs of points.
More formally:
We can use the product rule to get:
C(n) = \frac{n \times (n-1)}{2}
Note — We divide by two to avoid double-counting of A \leftrightarrow B and B \leftrightarrow A
Analysis — Time complexity is O(n^2) since we compute the distance for \frac{n(n-1)}{2} pairs. Space complexity is O(1) beyond storing the points.
Strengths
Weaknesses
A brute force solutoin to a problem involving search for an element with a special property, usually among combinatorial objects11. Mathematical structures constructed from finite sets according to specific rules. such as permutations, combinations, or subsets of a set.
Method: Systematically generate each possible combination, subset, or permutation, evaluate it against the problem constraints, and keep track of the best or valid solution found.
Note — On Performance: Exactness is Costly
- Runs in realistic time only on very small instances.
- In some cases, there are better alternatives.
- In many cases, exhaustive search or a variation is the only known way to get an exact solution.
Given n cities with known distances between each pair, find the shortest tour that passes through all the cities exactly once before returning to the starting city.
Generate all permutations of cities, calculate the total distance for each, and pick the shortest tour.
There are (n-1)! ways to traverse this22. i.e., 4 \times 3 \times 2 \times 1..
Find most valuable subset of items that fit into the knapsack.
Generate all 2^n subsets of items. For each subset, check if its total weight exceeds the knapsack capacity. If it doesn’t, calculate its total value. Find the maximum value among all valid subsets. The complexity is \Theta(2^n).
Assign n people to n jobs such that the total cost is minimized.
The exhaustive solution generates all n! permutations of assignments, calculates the cost for each, and selects the minimum. This is an O(n!) solution!