Do not attempt this problem until you have solved
The Hardest Prisoner Problem Ever (Part 1) and
The Hardest Prisoner Problem Ever (Part 2).
This problem is the same as Part 1 except:
Assuming that the prisoners use the fastest possible strategy, approximately how long will the game take as a function of the number of prisoners, ? (i.e. what is O(fastest strategy)?)