Celebrity

Computer Science Level 2

A celebrity among a group of $n$ people is the one who knows nobody but is known by everyone else.

You go to a party and wonder if there is any celebrity. You can figure that out only by asking questions in the form "Do you know this person?"

Provided you ask optimally, what is the complexity of the number of times you have to ask the question to identify the celebrity or conclude that he/she doesn't exist?

O(1)

O(n)

O(n\log n)

O(n^2)

1 solution

Calvin Lin Staff
Oct 22, 2016

To find if there is any celebrity, we have to ask at least $n-1$ questions for the form "Person $i$ , do you know person $j$ ?", where $i$ goes from 1 to $n$ , other than $j$ .

Conversely, we will show that $2n$ questions is sufficient.

Each time we ask "Person $i$ , do you know person $j$ ?", if the answer is Yes, then $i$ is not a celebrity. If the answer is No, then $j$ is not a celebrity.
We proceed as follows:
Start with $i = 1, j = n$ . Ask: Person $i$ , do you know person $j$ ?
If yes, we increase $i$ by 1.
If no, we decrease $j$ by 1.

The $n-2$ question is of the form: Person $k$ , do you know person $k+1$ ?
If the answer is yes, then we have eliminated everyone other than $k+1$ as a celebrity.
if the answer is no, then we have eliminated everyone other than $k$ as a celebrity.
We just have another at most $n-1$ questions to ask everyone else if they know the potential celebrity.

Hence, $2n-3$ questions is sufficient, so the order of complexity is $O (n)$ .

Celebrity

1 solution

0 pending reports