algorithmdata-structurestime-complexitycomplexity-theorygraph-algorithm# Optimal solution for the "celebrity" algorithm

Among `n`

persons,a "*celebrity*" is defined as someone
**who is known by everyone but does not know anyone**. The
problem is to identify the celebrity, if one exists, by asking the
question only of the form, "*Excuse me, do you know the person
over there?*" (The assumption is that all the answers are correct,
and even that celebrity will also answer.)
The goal is to minimize the number of questions.

Is there a solution of the order less than the obvious `O(n^2)`

here?

Solution

Using the analysis of the celebrity problem here

Brute-force solution.The graph has at most`n(n-1)`

edges, and we can compute it by asking a question for each potential edge. At this point, we can check whether a vertex is a sink by computing its indegree and its outdegree. This brute-force solution asks`n(n-1)`

questions. Next we show how to to do this with at most`3(n-1)`

questions and linear place.

An elegant solution.Our algorithm consists of two phases: in the elimination phase, we eliminate all but one person from being the celebrity; in the verification phase we check whether this one remaining person is indeed a celebrity. The elimination phase maintains a list of possible celebrities. Initially it contains all`n`

people. In each iteration, we delete one person from the list. We exploit the following key observation: if person`1`

knows person`2`

, then person`1`

is not a celebrity; if person`1`

does not know person`2`

, then person`2`

is not a celebrity. Thus, by asking person`1`

if he knows person`2`

, we can eliminate either person`1`

or person`2`

from the list of possible celebrities. We can use this idea repeatedly to eliminate all people but one, say person`p`

. We now verify by brute force whether`p`

is a celebrity: for every other person`i`

, we ask person`p`

whether he knows person`i`

, and we ask persons`i`

whether they know person`p`

. If person`p`

always answers no, and the other people always answer yes, the we declare person`p`

as the celebrity. Otherwise, we conclude there is no celebrity in this group.

- How to build a Minimum Spanning Tree given a list of 200 000 nodes?
- Edmonds maximum matching algorithm in PHP
- Divide an integer range into nearly equal integer ranges
- Maximize distance while pushing crates
- Increasing relevancy of search results
- Algorithm for ring or hollow artifact detection in binary images
- JavaScript - Flatten nested JSON object
- Convert a sorted array into a height-balanced binary search tree by picking middle element -- why does it work?
- Algorithm for iterating over an outward spiral on a discrete 2D grid from the origin
- Search in sorted array
- Are there known implementations of the CIEDE2000 or CIE94 Delta-E color difference calculation algorithm?
- How to find the time comlexity when comparing sublists?
- find minimum sum of non-neighbouring K entries inside an array
- How is my algorithm for stock span problem incorrect?
- How to efficiently check whether x appears before y in a list
- How do I find the closest possible sum of an array's elements to a particular value?
- Floydâ€“Rivest vs. Introselect algorithm performance
- Unexpected Invalid Memory Access in Recursive Function for Unique Number Search in CodeWars Challenge
- Find the number of valid substrings
- Template Matching Subpixel Accuracy
- Algorithm: Function to resolve degrees to x,y for drawing SVG Pie Graphs
- Smallest number that cannot be formed from sum of numbers from array
- Minimum steps to make all array values equal to each other
- Why do we say that finding a string in a hash table is O(1)?
- Why do we use the term "non-descending" instead of "ascending" in sorting algorithms?
- Time Complexity of Backtracking solution - Leetcode 473. Matchsticks to Square
- Image Processing: Algorithm Improvement for 'Coca-Cola Can' Recognition
- Find the supersequence of given ordered subsequences in Java
- What's a fast way to identify all overlapping sets?
- minimax losing only in one case of tic-tac-toe