When professors have to hand back exams to classes of 100 or more students in lecture halls like Strosacker or Rockefeller, a common practice is to have the class line up while the professor searches a stack of unsorted exams, one by one, until every student has their test.

This method, however, is algorithmically inefficient, wasting both the professor’s and the student’s time. One can mathematically see that sorting the test for return provides a significant decrease in the time required to hand back the exams.

Consider two classes, each with 100 students, taught by Professors A and B respectively. Assume that the professor can’t find certain tests faster by remembering where they are in the pile from previous searches. This may seem like an overly simplistic constraint; however, in practice many professors have each student leaf through the pile themselves, making this a reasonable assumption.

First, take the case of Professor A. This example will consider the worst case, to obtain an upper bound, where the students approach the instructor in the order opposite that of the test in the stack. From this, it follows that the professor will have to look at 100 exams for the first student, 99 for the second, and so on. Note then that the of the number of times the professor has to check if a test belongs to a student is the sum of all natural numbers between 1 and 100, which is 5,050. If each comparison takes one second, the upper bound time for the professor to hand back the exams is a whopping 85 minutes.

Now, consider Professor B. Professor B is smart, she numbers all her tests 1-100, and assigns each student a number. When they come up to her, they tell her their number and she looks through a stack of sorted exams. If we assume Professor B starts each search at the middle of the pile and then divides the stack in half successively until she finds the exam, again in the worst case, it will take the professor log base 2 of n trials to find any exam, where n is the number of tests currently in the pile. Thus, it follows that the total number of comparisons is the sum of all these values with n from 1 to 100. This number is about 525 which implies that the worst case test return time for this method is less than nine minutes, in stark contrast to the 85 minutes that it took Professor A.

Those familiar with algorithmic analysis will not be surprised by this fact. This is because the method used by Professor A falls into a notoriously slow class of algorithms known as big O of n squared, while the method used by Professor B is part of a much faster class of algorithms known as big O of n log n. The reasons for this are beyond the scope of this article, however; interested readers should investigate the asymptotic analysis of algorithms for a detailed explanation. But theory aside, this example shows, albeit non-rigorously, that with a little math, and a little thought students and professors alike can all spend a little less of their lives waiting in lines.