Coyote Tracks

I sometimes imagine how I would teach certain concepts, if I were put in charge of a class. (Not just in programming, either; many people who know me have said I’d make a great teacher; perhaps I’ve taken it to heart.) One of the concepts in programming that I feel has a particularly poor “ease-of-teaching versus importance-of-knowing” ratio is algorithmic complexity, best described using Big O Notation.

I just came across a great example of one use of Big O Notation, in examining the trade-off between conciseness and efficiency in Perl functions to find the smallest member of an array. While looking around for a good Levenshtein algorithm implementation, I noticed this helper function:

# minimal element of a list
#
sub min
{
    my @list = @{$_[0]};
    my $min = $list[0];

    foreach my $i (@list)
    {
        $min = $i if ($i < $min);
    }

    return $min;
}

And I thought, "Hmmm, that's a little odd. Why go through that entire loop, when you could just do:"

sub min {
	my @list = @{$_[0]};
	return (sort @list)[0];
}

Of course, hard on its heels came the thought: "Wait a second... how do those stack up in Big O?"

Without even bothering to look at the source code, I'll assume Perl's sort() is an implementation of Quicksort, and will achieve O(n log n) performance on most sane data. But the min() function supplied at Merriam Park is O(n); for any situation where log n is greater than 1, the n log n function will take longer than the just-plain n algorithm.

This would make a wonderful "teachable moment": point out to the class that my function is shorter, and easier to read and understand, but the other one is more efficient. This is exactly the sort of thing that Big O Notation is useful for, and it's something that can't be easily expressed just by looking at the code itself.

(Not that I'd try to tell the class that one way or the other was automatically better. The real usefulness of this example is the way the psychological complexity and the computational efficiency are in opposition to each other. It makes a great springboard to talk about how we decide on what trade-offs to make in engineering.)