A celebrity among a group of n people is a person who knows nobody but is known by everybody else. The task is to identify a celebrity by only asking questions to people of the form ""Do you know him/her?"" Design an efficient algorithm to identify a celebrity or determine that the group has no such person. How many questions does your algorithm need in the worst case?

In the first case the complexity is 0 (n) and in the second one the complexity is 0 (n^2).

Explanation:

Consider that the celebrity is recognized to exit among give "n" group of people.

The following algorithm are:

If n=1,

that one person is inanely a celebrity by a definition.

If n>2,

than choose 2 people from "n" group "A" and "b" and ask whether "A" is knows "B", remove "A" from remaining people from who can be celebrity.

If "A" dose not know's "B", than remove "B".

Than solving the problem from the same recursively method from the same "n" group until the "n-1" group of people who can be the celebrity.

Here, the complexity is 0 (n).

In the Next Case:

Visit to each of the person and ask them that the resulting "n-1" the best and the worst case of 0 (n^2)