Attendance

Chris is a teacher teaching a class of approximately \(10^{100}\) students. The most annoying thing about teaching this huge number of students is when the school principal asks "Is student with ID \(x\) present?" and you have to go through the list of students. Chris figured out 4 methods to make his life easier but he isn't sure which is the best.

  1. Sort the list of students according to their IDs. Then binary search for the ID e ach time the principal asks about a student.
  2. Sort the list of students according to their IDs. Then look through the list from the beginning each time the principal asks about a student.
  3. Leave the list of students as it is. Look through the list from the beginning each time the principal asks about a student.
  4. Leave the list of students as it is. Binary search for the ID each time the principal asks the about a student.

Based on the assumption that the school principal doesn't actually care about the students, and he might only asks around \(7-8\) questions throughout his entire lifetime, what is the best strategy in general you should suggest Chris?

Details and Assumptions

  • Sorting takes \(O(n\lg n)\) time.

  • Before sorting, the list is not in order.

×

Problem Loading...

Note Loading...

Set Loading...