Suppose there are n (mostly) identical robots in a room, each of which is capable of

testing each other for speed. The testing equipment can test 2 robots at a time. During

the test each Robot will tell whether the other one is fast or slow. A fast robot always

reports correctly whether the other one is fast/slow. But the answer of a slow robot

cannot be trusted.

The possible outcomes are

```
R1 Reports |R2 reports |Comment
R2 is fast |R1 is fast |Both are fast, or both are slow
R2 is fast |R1 is slow |at least one is slow
R2 is slow |R1 is fast |at least one is slow
R2 is slow |R1 is slow |at least one is slow
```

**Consider the problem of finding one fast robot from among n robots**

*Assumption: More than half of the robots are fast*.

a. Give and solve the recurrence that describes the number of tests T(n) needed

to find a single fast robot from n robots. *Hint: Number of tests needed to*

reduce the problem size to half=n/2 (robots tested in pairs)

b. Show that all Fast Robots can be identified with O(n) tests (tests done in

pairs).

This is part of one of sample assessment questions.

b. Show that all Fast Robots can be identified with O(n) tests (tests done in

pairs).

In case of fast robot I am able to understand that only 1 comparison is needed and that is why we are getting O(n) as order of test.

a. Give and solve the recurrence that describes the number of tests T(n) needed

to find a single fast robot from n robots. *Hint: Number of tests needed to*

reduce the problem size to half=n/2 (robots tested in pairs)

I think the worst case will appear when we will get fast robot after getting all the slow robots. Thing I am not able to determine is how I will decide that robot is slow or we have encountered a fast robot?

I am also not able to determine the type of the problem.

I am looking for some direction to solve this problem.