Handbags and Big O Notation

One of the more entertaining projects I did at university was to research how people stored their belongings about their person. Tenuous as the link between that and Information Systems might seem, there’s some interesting stuff to consider.

There are several aspects of a person’s Physical Storage & Retrieval System (PSRS):

  1. Storing stuff, so you can take it with you.
  2. Finding and retrieving stuff, so you can use it.
  3. Checking that you have the right stuff when you rush out of the house in the morning.

There are two main classes of people, you’re probably familiar with them:

  • Boys, who keep things in their pockets.
  • Girls, who keep things in a bag.

I know there are exceptions to these categories – let’s not even get started on people who wear backpacks with both straps and people who keep things in their shoes – but these are the main types of PSRSs we came across on our project.

Being a boy, I’ll discuss the pocket method first. This is a very simple, somewhat inflexible system that relies on something anthropologists call The Ritual of the Patting which we’ll come to in a moment. Every item has a designated pocket, and every pocket has a single designated item. There are variations, but popular configurations are Phone-Keys-Wallet and Keys-Cash-Phone-Wallet. The main advantage of this method is that you are left with a highly optimized lookup table of possessions – if you want your to store or retrieve your phone, you go to the Front-Left pocket, say, and if you want your wallet, you go Back-Right. The Ritual of the Patting is the system whereby pocket integrity is maintained. Upon leaving the house, the car or a meeting, each pocket emplyed in the system is patted once to confirm the presense of its designated object. The object is assumed to be the right one, as the pocket designations are
deeply ingrained over a period of years. Of course the drawbacks of this system are the limited number of pockets, any overflow of which usually ends up in the wallet. In this case, the pockets become a cache of regularly used items, and the wallet becomes a much slower storage mechanism of its own.

Unlike the pocket method, the handbag method requires no configuration, beyond choosing a bag you like. All useful possessions, and several weeks’ worth of receipts and lint, are stored, un-indexed, in a single pile inside the bag. Everything a girl could need must be stored in the bag, giving the advantage over The Ritual of the Patting that everything required for the day can be assumed to be in the bag at all times. Storage of items, upon switching bags for example, is very quick, as each item is merely thrust into the gaping maw of the new bag. Where this system falls down, of course, is in retrieval of items. This requires the retriever to rummage around hoping to catch a glimpse or cop a feel of the correct item. The more items in the bag, the longer this takes.

We can capture the complexity of the two systems in big O notation thusly:

  • Pockets – Storage: O(n); Retrieval: O(1); Checking: O(n)
  • Handbag – Storage: O(1); Retrieval: O(n2); Checking: O(1)

Therefore, assuming every item has to be stored, checked and retrieved once a day, the total complexity of the pockets system is n + 1 + n = 2n + 1, and the handbag system is 1 + n2 + 1 = n2 + 2.

Therefore, for all values of n greater than 1, boys are more efficient. Case proved.

This entry was posted in Computer Science and tagged , , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>