Celebrity Problem

Problem. In a party of $n$ people, a celebrity is someone whom everyone knows and who knows nobody. Given only the query knows(a, b), find the celebrity or report that none exists.

The $O(n)$ elimination

Each query eliminates one candidate:

$\text{if }\mathrm{knows}(a,b):a\text{ is not the celebrity};\text{else}:b\text{ is not.}$

int findCelebrity(int n) {
    int cand = 0;
    for (int i = 1; i < n; i++)
        if (knows(cand, i)) cand = i;               // cand knows i -> cand is out
        // else i knows... no: i is out, keep cand
 
    for (int i = 0; i < n; i++) {                   // VERIFY
        if (i == cand) continue;
        if (knows(cand, i) || !knows(i, cand)) return -1;
    }
    return cand;
}

$n-1$ queries to find the candidate, then $2(n-1)$ to verify — $3n-3$ total, or $3(n-1)$ in the worst case.

Verification is mandatory

The elimination phase finds the only possible celebrity, not a confirmed one. If no celebrity exists, it still returns someone. Skipping the second phase is the standard bug.

Why one query eliminates one person

• If knows(a,b) is true, then $a$ knows someone, so $a$ is not a celebrity.
• If it is false, then $b$ is not known by everyone, so $b$ is not a celebrity.

Either way one candidate dies, so $n-1$ queries leave exactly one survivor. And since a celebrity, if it exists, is never eliminated, the survivor is the only possibility.

The lower bound

$3n-\Theta (\log n)$ queries are necessary in the worst case, so the simple algorithm is optimal up to lower-order terms. The verification phase can be trimmed slightly (some pairs are already known from phase 1), which is where the $\log n$ saving comes from.

The graph view

Model “knows” as a directed graph. A celebrity is a vertex with

$\text{in-degree }=n-1,\text{out-degree }=0.$

• At most one can exist (two celebrities would have to know each other).
• With the full adjacency matrix, finding it is $O(n^2)$ by summing rows and columns — but the $O(n)$ algorithm never reads most of the matrix.

That gap is the interesting part: the answer is determined by $O(n)$ of the $n^2$ entries.

The general technique: elimination by pairwise comparison

Each comparison removes one candidate; $n-1$ comparisons leave one; then verify.

Problem	Comparison	Verification
Celebrity	knows(a,b)	check in/out degrees
Majority element	equal or not	count occurrences
Maximum of $n$	$a<b$	none needed
Tournament winner	who beats whom	check it beats everyone
The “heavier coin”	balance	weigh against a known-good
Finding a sink in a DAG	edge direction	check out-degree 0

Majority and celebrity share the same shape: a linear elimination pass that finds the only candidate, followed by a verification pass. Recognising that pattern makes both algorithms easy to reconstruct.

Variants

Variant	Note
Celebrity may not exist	the verification handles it
Several celebrities	impossible — at most one
”Almost celebrity” (knows at most $k$)	needs more queries
Adjacency matrix given	$O(n)$ with the same algorithm, or $O(n^2)$ by summing
Find a sink in a tournament	every tournament has a Hamiltonian path; a sink may not exist
Interactive version with a query limit	the $3n$ bound matters

Why it is worth knowing

It is the cleanest demonstration that an algorithm can beat the input size: with $n^2$ possible relationships, only $O(n)$ of them need to be examined. Whenever a problem gives you an $n\times n$ relation and asks for something with a strong uniqueness property, look for an elimination argument before reading the whole matrix.

See also: Majority Element · Graph Fundamentals · Extremal Principle