Big-oh is not a total order

Thursday 21 July 2011, 10:34

Anyone 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:44

Imagine 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.

First thoughts on Google Plus

Wednesday 13 July 2011, 14:19

M. "Doc" Skala tries things so you won't have to!

Bonobo Conspiracy - comments

Sunday 3 July 2011, 08:46

Here's the comment thread for my Bonobo Conspiracy archive posting.

Bonobo Conspiracy

Sunday 3 July 2011, 08:30

In 2005 through 2008 I wrote and posted a Web comic called Bonobo Conspiracy. I posted a new strip with a new joke every single day for just over 1000 days, chronicling the lives, thwarted romances, and mad science of Matt, Sun-Moon, Dr. Klaun, Algea, and a host of special guests. Although most strips were designed to stand on their own, I also gradually developed each character over the course of the run, and I ran a few multi-strip specials and storylines.

"Grimoire" fonts

Sunday 26 June 2011, 10:15

Here'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.

Stimulants

Friday 10 June 2011, 09:53

I wonder: what percentage of current agricultural capacity is devoted to stimulant drug crops? I mean tea, coffee, tobacco, khat, areca, coca, cacao, yerba mate, and so on. It seems like it must be a pretty large percentage. I wonder how much food could be grown using those resources, and how that amount of food compares to the size of the food shortage.

Don't get me wrong, I'm not saying that it would be possible or desirable to make such a substitution. It seems like there must be a reason that nearly every human culture has a tradition of using stimulant drugs. Also, I'm well aware that different plants grow under different conditions, so the land and resources currently used for non-food crops can't necessarily be used for food crops. But it would still be interesting to know the answers to the questions.

Plaid code

Thursday 19 May 2011, 15:45

Fans of my fiction writing will doubtless remember my theory that in the Future, girls' school-uniform skirts will be made of "smart fiber," capable of changing colour under computer control to act as a sort of display screen, and the wearers will use that to encode personal information into the plaid stripes of something like a present-day 2D barcode. Such technology already exists today (it's closely related to "e-paper"), though it isn't cheap and rugged enough yet for serious use in clothing.

Well, in one of my nefarious projects I recently had occasion to actually use a data-to-tartan encoding scheme, and you might find the results interesting. Here's a sample:

[Plaid code swatches]

See if you can reverse-engineer the encoding that generated those swatches. It's quite simple, and has an historical basis.

Tarot spread generator

Saturday 14 May 2011, 11:26

Here's a simple online Tarot page I wrote a few years back. Very simple: choose a spread, you see the cards face-down, click on each card in turn to flip it face-up. You're on your own for interpretation. I'm taking the opportunity of the transition to the new site code, to add a Project Wonderful box - but if I'm not pleased by the bidding on that, I may remove it.

The card images used in this system are scans from the edition of the Waite deck published in 1909 that collectors call "Pamela-A," and they are public domain in Berne Convention countries. See John B. Hare's comparison of the Pamela-A deck with another popular deck.

Gas prices and the Conservative tax on everything

Friday 13 May 2011, 07:04

I'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.