Celebrity Problem

There are a group of people with one celebrity. Everyone knows the celebrity but the celebrity knows no one. You can ask questions such as “Does A know B?” How can you find the celebrity in the fewest number of questions? Let $K(X,Y)$ denote the boolean “X knows Y”

Brute Force: $O(n^2)$

• Ask everyone if they know everyone else and see who it is everyone knows or who it is that knows no one

Stack: $O(n)$

• Make a stack of potential celebrities (initially contains everyone)
• While the stack size is greater than 1
  • Pop two people off the stack, call them $A$ and $B$
  • If $K(A,B)$
    • $A$ is not the celebrity, so remove them and push $B$ back onto the stack
  • Else
    • $B$ is not the celebrity, so remove them and push $A$ back onto the stack
• The last person in the stack is the celebrity
  • If we are assuming there can be 0 celebrities, then we need to double check here by asking everyone if they know this person and asking this person if they know anyone else