Consider the following three algorithms for determining whether anyone in the ro
ID: 3669249 • Letter: C
Question
Consider the following three algorithms for determining whether anyone in the room has the same birthday as you.
Algorithm 1: You say your birthday, and ask whether anyone in the room has the same birthday. If anyone does have the same birthday, they answer yes.
Algorithm 2: You tell the first person your birthday, and ask if they have the same birthday; if they say no, you tell the second person your birthday and ask whether they have the same birthday; etc, for each person in the room.
Algorithm 3: You only ask questions of person 1, who only asks questions of person 2, who only asks questions of person 3, etc. You tell person 1 your birthday, and ask if they have the same birthday; if they say no, you ask them to find out about person 2. Person 1 asks person 2 and tells you the answer. If it is no, you ask person 1 to find out about person 3. Person 1 asks person 2 to find out about person 3, etc.
Question 1: For each algorithm, what is the factor that can affect the number of questions asked (the "problem size")?
Question 2: In the worst case, how many questions will be asked for each of the three algorithms?
Question 3: For each algorithm, say whether it is constant, linear, or quadratic in the problem size in the worst case.
Explanation / Answer
Question 1.
Answer:- Problem size is number of people in room.
Question 2.
Answer:- Assuming that there N number of prople in room. For algorithm 1 we ask one question. For algorithm 2 tthe worst case is if no one has your birthday. To figure out we have to ask every person. This is a N question. For algorithm 3, the worst case it is same as algorithm 2. The number of questions will be 1 + 2 + 3 + ... + N-1 + N.
Question 3.
Answer:- We can see that algorithm 1 is in constant time, algorithm 2 is in linear time, and algorithm 3 is in quadratic time in problem size.