{"id":31,"date":"2009-05-02T18:39:04","date_gmt":"2009-05-03T01:39:04","guid":{"rendered":"http:\/\/kai.mactane.org\/blog\/2009\/05\/02\/on-complexity-versus-efficiency\/"},"modified":"2015-10-28T23:07:37","modified_gmt":"2015-10-29T06:07:37","slug":"on-complexity-versus-efficiency","status":"publish","type":"post","link":"https:\/\/kagan.mactane.org\/blog\/2009\/05\/02\/on-complexity-versus-efficiency\/","title":{"rendered":"On Complexity Versus Efficiency"},"content":{"rendered":"

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<\/em>, best described using Big O Notation<\/a>.<\/p>\n

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<\/a>, I noticed this helper function:<\/p>\n

# minimal element of a list\r\n#\r\nsub min\r\n{\r\n    my @list = @{$_[0]};\r\n    my $min = $list[0];\r\n\r\n    foreach my $i (@list)\r\n    {\r\n        $min = $i if ($i < $min);\r\n    }\r\n\r\n    return $min;\r\n}<\/pre>\n
And I thought, \"Hmmm, that's a little odd. Why go through that entire loop, when you could just do:\"<\/p>\n
sub min {\r\n\tmy @list = @{$_[0]};\r\n\treturn (sort @list)[0];\r\n}<\/pre>\n
Of course, hard on its heels came the thought: \"Wait a second... how do those stack up in Big O?\"<\/p>\n
Without even bothering to look at the source code, I'll assume Perl's sort()<\/code> is an implementation of Quicksort<\/a>, and will achieve O(n log n)<\/var> performance on most sane data. But the min()<\/code> function supplied at Merriam Park is O(n)<\/var>; for any situation where log n<\/var> is greater than 1, the n log n<\/var> function will take longer than the just-plain n<\/var> algorithm.<\/p>\n
This would make a wonderful<\/em> \"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<\/em>. 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.<\/p>\n
(Not that I'd try to tell the class that one way or the other was automatically<\/em> 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.)<\/p>\n","protected":false},"excerpt":{"rendered":"
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 […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[34,32,33,31],"_links":{"self":[{"href":"https:\/\/kagan.mactane.org\/blog\/wp-json\/wp\/v2\/posts\/31"}],"collection":[{"href":"https:\/\/kagan.mactane.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/kagan.mactane.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/kagan.mactane.org\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/kagan.mactane.org\/blog\/wp-json\/wp\/v2\/comments?post=31"}],"version-history":[{"count":4,"href":"https:\/\/kagan.mactane.org\/blog\/wp-json\/wp\/v2\/posts\/31\/revisions"}],"predecessor-version":[{"id":627,"href":"https:\/\/kagan.mactane.org\/blog\/wp-json\/wp\/v2\/posts\/31\/revisions\/627"}],"wp:attachment":[{"href":"https:\/\/kagan.mactane.org\/blog\/wp-json\/wp\/v2\/media?parent=31"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/kagan.mactane.org\/blog\/wp-json\/wp\/v2\/categories?post=31"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/kagan.mactane.org\/blog\/wp-json\/wp\/v2\/tags?post=31"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}