Big-oh is not a total order
Wednesday 31 December 1969, 16:00Anyone who's studied computer science should be familiar with the Landau asymptotic notation, or "big-oh" notation. But how well do you really know it?
Given two functions it seems intuitive that one at least one ought to be big-oh of the other; in some cases maybe they are both big-oh of each other, in which case they are theta of each other and in a certain sense can be said to be equivalent. It sure feels like a total order, with a place for everything and everything in its place, and it is a total order on all the kinds of functions we normally care about. I've certainly marked down plenty of students for incorrectly claiming that n log n can't be compared either way to things like n and n2.
But today I had occasion to wonder if it's really true that O() induces a total order on all functions for which it is applicable. I looked on the Net and couldn't find anyone discussing this issue; I did find this archived final exam in which someone asked it of students as a true/false question and apparently was looking for the answer "true." Unfortunately, the correct answer is "false."
Counterexample below the cut. If you've got a computer science background you might want to think about it a bit yourself before going further. It shouldn't really be hard if you look carefully at the definition.
The parable of the tricycle
Saturday 26 July 2008, 20:44Imagine a young man nearing his 16th birthday, the day when he'll be eligible to get a driver's license. And let's imagine this is before graduated licensing was a big thing, or else imagine that he's maybe a little older and getting ready for the final level of the graduated system instead of the first level, or something like that. The point isn't exactly his age, just that he's about to get to the point where having a vehicle of his own would be a pretty good thing.
"Grimoire" fonts
Sunday 26 June 2011, 10:15Here's a project that provides, among other things, free vector fonts of magical glyphs from the Lesser and Greater Keys of Solomon. I found it by way of sourceforge.jp's flagging it as a similar project to Tsukurimashou.
Gas prices and the Conservative tax on everything
Friday 13 May 2011, 07:04I've been hearing a lot of grumbling about gasoline prices recently. People who ought to know better on my social-networking friends lists circulated that asinine one-day "boycott" message a little while back. My alarm clock wakes me with CBC Radio every morning, and today they were talking to someone from Consumer's Union who was hoping to pressure the Federal government to Do Something. I'm of the opinion that the Federal government has already Done way too Much in this matter, and they ought to butt out already.
One of Harper's talking points in the recent election was to accuse the Liberals of pressing for a "tax on everything" (a scary renaming of the carbon tax that anybody who cares about survival of the planet, including a clear majority of Canadians, actually supports). But when you fill up your car's gas tank and pay today's prices for it, you are paying the Conservative tax on everything, which they implemented without a vote and which never received proper discussion or coverage. Let's put the blame where it belongs.
Disclosure: I don't own a car, and I do own units of a real-return bond index fund, which makes more profit in nominal terms when the price of everything (including gasoline) goes up. I don't think that really means I benefit from higher prices, only that I lose less than some other people. I've written about inflation-indexed bonds before. I'd rather have prices stay low and my bonds not make so many dollars.
Dream: a box of cards
Monday 18 April 2011, 08:06Dream transcript from the morning of May 2, 2009. I posted it in my Dreamwidth journal at the time, and I'm pretty sure I know what it meant because it tied into events in my life at the time, but I felt like posting it again today.
４月１７日の日記
Sunday 17 April 2011, 13:01久しぶりに日記を書きました。日本語の勉強したいので、ここによく書くようにしています。しかし難しいです。たいていな友達は日本語をよめません。読まなかったら、書き物の意味ありませんか？
Fixing Alpine's broken subject sort
Monday 4 April 2011, 10:09I use the Alpine email software, which is successor to Pine. I mostly like it, but its implementation of "sort by subject" is broken and annoying.
It is documented that Alpine will strip "Re: " and variations from the start of a subject line before sorting, and that seems like something I would reasonably want: replies end up getting sorted with the things they are replies to, instead of all being grouped confusingly under "R". However, what is undocumented and unwelcome is that Alpine will also look for and remove strings enclosed in square brackets, which are typically used to identify mailing list messages. I subscribe to several mailing lists that identify themselves by square-bracketed tags at the start of the subject line while leaving the From: headers unchanged (messages are from the person who sent them instead of from the list). If subject sort worked, then as a natural consequence of how string sorting works, I could group all messages from the list together, sorted within the group by the rest of the subject. But because square-bracketed tags are silently ignored, I can't do that, and there is no way to group the mailing list messages together. There is no option to make subject sort sort on the actual subject, no really, the string that is in the Subject: header and not a munged version.
Fixed by deleting lines 4562 to 4565 of imap/c-client/mail.c in the Alpine 2.00 distribution, which check for square brackets and invoke mail_strip_subject_blob().
Henry and Eliza
Friday 7 June 2002, 14:21Henry came home from work feeling as horny as Hell. He threw his coat across the back of a chair, kicked off his boots, and picked up the mouse from its spot on top of the pile of books on the kitchen table, next to the breakfast dishes. He didn't shower. Eliza wouldn't care.
Chinese Seal Script fonts
Friday 25 February 2011, 06:51Here's a page of Chinese fonts including a few for the Seal Script. Could come in handy...
How Wikipedia could save itself
Saturday 19 February 2011, 00:15I don't think Wikipedia wants to save itself. But if they really wanted to, I know how they could do it.
