[ SB Coded ]

You’re grading two pieces of code handed to you; which of the two gets a better grade?

• The code that sorts a list of items in O(nlg(n)) for all n
• The code that sort in O(n²) but performs faster for n < 100

Should students be graded on the real-world performance of their programs? I am a TA for a data structures/C++ course and someone asked: “Do we grade performance?” The knee jerk answer was an unequivocal: “YES!“. But now, I’m not so sure anymore. The data structures that are taught and used to give structure to our data; sometimes we get lucky and that structure gives as faster running programs.

Do we ever ask students to write fast code instead of theoretically fast code? How should something like timsort ( O(nlg(n)) for large values of n, but behaves like O(n²) for small values of n) be graded versus the more theoretically pure mergesort?

I find quicksort to be a great example when thinking about real world versus theory world. Quicksort is a magical algorithm that theory tells us runs in  O(n²) but in the real world it tends to behave nicely and within the bounds of O(nlg(n)). But now comes the weird part: Quicksort can actually be implemented to run in honest-to-goodness O(nlg(n)) (An algorithm does exist to find the median of a list in O(n) see wikipedia here). But that implementation is such a pain to code and the constants hidden in that O(n) are so evil, that you would mad to implement it. In fact, I would probably much rather implement timsort. But I would then have to be weary of my algorithms professor ever looking at my code. Specifically, I had a professor who very specifically ingrained into my mind that bubblesort is NEVER the answer. But maybe the right answer is: never bubble sort large arrays.

We teach our students things like debuggers and memory checkers, does it make sense to add “profiler” to their arsenal of tools? Should real-world performance of their code also be factored into their grades? Do we have so little faith in our students that we’re afraid that they’ll create horrific messes of code if we focus on making them write faster code?