There is a group of n people, some of them know each other. One of the people he

Question

There is a group of n people, some of them know each other. One of the people heard a rumor, that he/she can secretly tell just to 1 person he/she knows. That person, in turn, can tell a rumor to other person and so on. If the person hear the rumor that he/she already know, this person will not share it with anyone else (assuming that if he/she heard it twice, than probably everybody knows it). You need to find out, is it possible that eventually everybody will hear the rumor?

Represent this problem as one of the algorithmic problems that we studied in our class. What is this algorithmic problem? Is it possible to solve it in a polynomial time?

Explanation / Answer

This problem is considered to be Polynomial time algorithm. Also it was considered to be
optimization / decision problem.

Yes this problem will solve it in Polynomial time.
Since when start hearing from one person to two persons and so on n levels, the number of poeple
hearing will be increased and definitely greater than previiusly listened people. So all people will
listen and people halt spreading of they listen twice. So definitely entire process will halt in
polynomial time.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.