# Celebrity Cliques In Optimal Time

**Computer Science**Level 4

A party \(P\) is a set of distinct people with a relation \(\text{knows}\).

A non-empty subset \(C\) of \(P\) 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,

\[ \forall x \in P, y \in C :: x \text{ knows } y \wedge (y \text{ knows } x \implies x \in C).\]

You wish to design an algorithm which takes in the number of people (\(n\)), and the matrix that describes the \(\text{knows}\) relation and determines if there is a *celebrity clique* in the party.

Which of the following is the sharpest lower bound?