Celebrity

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?

×

Problem Loading...

Note Loading...

Set Loading...