Foundations — Brute force — exhaustive search, when acceptable

This page assumes you have seen nothing. Every symbol below is earned before it is used. It is the prerequisite floor for the parent topic, which sits inside Algorithm Paradigms.

0. The absolute-zero starting point: what is a "candidate"?

Before any symbol, one word: candidate. A candidate is a single possible answer you might hand in — one guess. Brute force is the act of writing down the complete list of all guesses and ticking each one.

Look at the figure: each amber dot is one candidate; the cyan box drawn around all of them is the search space. Brute force = visit every dot. The whole rest of this page is just counting how many dots there are for the common shapes of problem — because that count is the running time.

1. The symbol $n$ — "how big is the input?"

Picture $n$ as the number of boxes in a row:

 box 1   box 2   box 3   ...   box n
[     ] [     ] [     ]  ...  [     ]

Why the topic needs it: every cost formula in the parent is written in terms of $n$. If we could not name "the size of the input", we could not say how the work grows. $n$ is the dial we turn to ask "what if the input gets bigger?"

2. The symbol $\le$ — "at most"

Picture a number line: $x\le y$ means $x$ sits at $y$ or anywhere to its left.

 <----|---------|---------|--------->
      x         y
      x is here or anywhere left of y

Why the topic needs it: constraints are always phrased as "$n\le 20$" (an upper bound on input size) and feasibility checks as "weight $\le W$" (must not exceed a cap). The whole "when is brute force acceptable?" table is a list of $\le$ bounds.

3. Multiplication as independent choices — the counting engine

Everything explosive in brute force comes from ONE idea: when you make several choices one after another and each choice is free of the others, you multiply the number of options.

Why the topic needs it: $2^n$, $n!$, and (later) $b^k$ are all just this rule applied over and over. Master this one picture and the scary formulas become obvious. We now derive each.

4. $2^n$ — the number of subsets

First, two sub-symbols.

Now the derivation, WHAT/WHY/PICTURE:

• WHAT we do: walk the items one by one, each time choosing in or out.
• WHY multiply: the choices are independent (choosing item 1 doesn't restrict item 2), so by the rule of product we multiply. There are $n$ items, each with $2$ options: $\underset{n}{\underbrace{2\times 2\times \cdots \times 2}}=2^n$.
• WHAT IT LOOKS LIKE: a branching tree that doubles at every level.

Count the leaves at the bottom of the figure: for $n=3$ items there are $2^3=8$ leaves — that is $8$ subsets, from the empty selection to the full one.

5. $n!$ — the number of orderings (permutations)

• WHAT we do: fill ordered slots left to right.
• WHY the numbers shrink: slot 1 can be any of the $n$ items. Once placed, only $n-1$ items remain for slot 2, then $n-2$, and so on. The choices are still independent in the multiply sense (any first choice pairs with any valid second choice), so we multiply: $n\times (n-1)\times \cdots \times 1=n!$.
• WHAT IT LOOKS LIKE: the same branching tree, but each level has one fewer branch than the last.

6. $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ — the number of unordered pairs

• WHAT we do: pick a first item ($n$ ways) and a second, different item ($n-1$ ways): that gives $n(n-1)$ ordered pairs.
• WHY divide by 2: each unordered pair got counted twice (once as $(a,b)$, once as $(b,a)$). Undo the double-count by dividing by $2$: $\left(\genfrac{}{}{0ex}{}{n}{2}\right)=\frac{n(n-1)}{2}$
• WHAT IT LOOKS LIKE: a grid of all $(i,j)$ cells; the diagonal (self-pairs $i=i$) is thrown out and the two triangles are mirror images — keep just one.

In the figure the cyan cells above the diagonal are the pairs we keep; the greyed-out diagonal is self-pairs, and the lower triangle is the duplicate we divide away. This is exactly why Worked Example 1 in the parent starts its inner loop at i+1.

7. $b^k$ — the number of length-$k$ strings over $b$ symbols

The parent's Example 3 cracks a PIN and quotes "$b^k$". Let us earn $b$ and $k$ from zero.

• WHAT we do: fill $k$ ordered slots; each slot can independently hold any of the $b$ symbols.
• WHY it is $b^k$: slot 1 has $b$ options, slot 2 has $b$ options, …, $k$ slots in all. Repeated independent choices → rule of product → $\underset{k}{\underbrace{b\times b\times \cdots \times b}}=b^k$. (Unlike permutations, symbols may repeat, so the count does not shrink to $b-1$ — every slot still sees all $b$ options.)
• WHAT IT LOOKS LIKE: the same branching tree as subsets, but each level now splits into $b$ branches instead of $2$.

8. Big-$\Theta$ and Big-$O$ — "how fast does the count grow?"

Why we throw away constants: we care about how the work scales when input grows, not the exact tick-count, which depends on your machine. Doubling $n$ makes an $n^2$ algorithm do $4\times$ the work — that ratio is the useful truth.

Why the topic needs it: the parent's whole acceptability table ($O(n!)$, $O(2^n)$, $O(n^2)$…) is written in this language. Without $\Theta$/$O$ we couldn't compare "$2^n$ at $n=18$" against "$n^2$ at $n=10^5$".

9. Bits, the AND operator, and bit-masks — turning a subset into a number

The parent's Example 2 loops for mask in range(1 << n) and tests mask & (1 << i). Decode it now.

$\text{items }(i_2,i_1,i_0)=(1,0,1)⟶\text{binary }101=5⟶\text{subset }\{i_0,i_2\}$

The test mask & (1 << i) builds the number $1\ll i$ (a single $1$ in slot $i$) and ANDs it against mask. The result is non-zero only if bit $i$ of mask is a $1$ — i.e. it asks "is item $i$ in this subset?". The & isolates that one bit and ignores all the others. This machinery is explored fully in Bitmasking.

Prerequisite map

Everything funnels into the parent: the counts tell you the search-space size, Big-$\Theta$/Big-$O$ tells you how fast it grows, and $\le$ constraints tell you whether it fits the time budget.

Where these foundations lead next

Once you can count the search space, you can decide whether to accept brute force or reach for a smarter paradigm — Dynamic Programming (reuse overlapping sub-answers), Greedy Algorithms (commit to locally-best moves), or Backtracking (prune dead branches early). For problems where no shortcut is known — NP-Hard Problems — brute force with pruning is often all we have.

Equipment checklist

Self-test: cover the right side, answer, then reveal.