A round-robin tournament with n players, where you have the results (win/lose) of all the games and you must determine whether there is a player who won all his games.
The input is the n(n-1)/2 bits indicating the results, but the existence of a winner can be determined in O(n) steps (fun exercise).
The input is the n(n-1)/2 bits indicating the results, but the existence of a winner can be determined in O(n) steps (fun exercise).