Celebrity Cliques In Optimal Time
A party is a set of distinct people with a relation .
A non-empty subset of is a celebrity clique if everyone in the clique is known by everyone in the party, but the members of the clique only know each other. Formally,
You wish to design an algorithm which takes in the number of people ( ), and the matrix that describes the relation and determines if there is a celebrity clique in the party.
Which of the following is the sharpest lower bound?
Inspired by Richard Bird's Pearls of Functional Programming
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
To show that Ω ( n ) is not a sharp enough lower bound, we notice that Ω ( n 2 ) can be achieved. And to show that the others are not lower bounds, we could come up with an explicit quadratic time algorithm to solve the problem.
Suppose there was an algorithm better than Ω ( n 2 ) , this means that this program is not inspecting at least one of the entries of the knows matrix. We'll show that without inspecting this entry, there cannot be any conclusion drawn about the celebrity clique at all.
True. This means that the entire party is a celebrity clique.False. Now, y is not a celebrity since x does not know him. But everyone else, still knows y , which means they are not celebrities either. At this point, only x could be a celebrity. But unless, x and y are the only people in the party, there is someone else that x knows, in which case there are no celebrities.Hence, the algorithm can never tell if there is a celebrity clique without inspecting all of the entries (at least once).