“Big O” Notation Personified

Big O Notation… once you get practicing, it starts to fall into place, but wouldn’t it be nice if there WAS a magic bullet, something to help you memorize it from the beginning? Now, there is, sort of. Meet the “Big O” Cast of Characters. NOTE: these are just the major players. O(1), O(n), O(n^2), O(n!)

One Eyed Constance – O(1) … One Eyed Constance would be O(1) or “constant” time complexity. Though it may seem counterintuitive to think that “One Eyed Constance” would symbolize “the best time complexity”, consider: If One Eyed Constance can do it, ANYBODY can. Also, though we see O(1), it doesn’t mean that only one thing happens… it could be many “one” things. Also: One Eyed Constance is a pirate. For example:

function wink(name, message) {
  console.log(name, message)
}

let oneEyedConstance = wink.bind()

function atTheBar() {
  oneEyedConstance("Cool Constance", "winks creepily at you.")
  oneEyedConstance("Cool Constance", "winks very creepily at you.")
  console.log(" ")
  oneEyedConstance("Cool Constance", "says 'pssst, I'm a pirate.'")
  oneEyedConstance("Cool Constance", "says 'ARRR matey!  Lost my eye while staring at me some fine booty'")
  console.log(" ")
  oneEyedConstance("Creepy Constance", "says 'they said, take a picture, it'll last longer, but I didn't listen, learned me lesson the hard way.")
}

atTheBar()

Some additional thoughts about One Eyed Constance: Constance can handle arithmetic operations and setting variables, but that’s about all. If operations are multiplicative, One Eyed Constance can’t handle it.

The mO(n)k – O(n) … “The Monk” represents O(n) time. The mO(n)k is the kind of dude or dudette that will go on a journey of 1000 miles, taking a single step at a time. The amount of time it takes The mO(n)k to complete a journey is based on how many steps (literally) there are. If you can “count” linearly how many steps there are in your code without thinking too hard about it, chances are The mO(n)k will make an appearance. Also, to help remember what O(n)/linear time looks like, picture your mO(n)k walking up a flight of stairs, especially as the relationship between operations and elements is direct. To illustrate…

journey = new Array(500)
function monkyThingToSay() {console.log("OM")}

function monk(journeyInSteps) {
  for (let step = 0; step < journeyInSteps.length; step++) {
    console.log('this is step ', step + 1)
    monkyThingToSay();
  }
}
monk(journey);

Owen the Square – O(n^2) … Owen the Square represents n “squared” time, or “quadratic” time complexity. As a shorthand, this is anything that would contain a nested loop. Run the code below on repl.it or playcode.io to let the tedium sink in.

const boringStories = ["a boring tale from the accounting department", "another boring tale from an internal audit", "a tale of tedium about a broken calculator", "a tedious tale about quadratic equations", "a story about quadratic run time that you didn't want to hear about"]

const reallyBoringTangents = ["made even worse by a tangent about quadratic time.", "made mind numbing with more boring examples from an actual spreadsheet.", "made confusing in addition to boring with a random anecdote about college.", "made extra miserable because Owen keeps laughing at his own jokes."] 

function owenTheSquare(stories, tangents) {
  for (let boringStory = 0; boringStory < stories.length; boringStory++) {
    for (let boringTangent = 0; boringTangent < tangents.length; boringTangent++) {
      console.log(stories[boringStory], tangents[boringTangent])
      console.log(" ")
    }
  } 
}

owenTheSquare(boringStories, reallyBoringTangents)

Last but not least we have:

Oni – O(n!) – an “Oni” in Japanese folklore is something of a troll, or ogre. A supernatural being that is most definitely bad… just like an algorithm that runs in factorial time! Chances are: any algorithm you code that runs in factorial time on an interview will result in a fa!l … It would essentially be nested loops for every input. Or nested loops for every input’s input and their grandmother. Not as bad as factorial time is exponential time. Suffice it to say that anything beyond O(n^2) will almost definitely be unacceptable. As a shorthand for determining that: if your code is self-evidently O(n^2) and you can’t understand it beyond that? Then you’re in trouble.

HEADS UP! These characters aren’t the only Big O “characters” you’ll meet. But, any other notations (characters) you might want to add will fit neatly between them, furthermore, the other notations are somewhat specific to certain types of algorithms.

As a final thought… remember, if you’re coding an algorithm where all of the above characters are present, and someone asks you: “so, what’s the Big O”, know that you only need acknowledge the most dominant character present. In other words: One Eyed Constance becomes a non-entity in the presence of The Monk, but Owen the Square’s un-enlightened personality will always overpower The Monk, but all will be overshadowed by an Oni.

It’s my belief that thinking of Big O in the context of characters, (and code that represents the essence of a character) will make it easier in the beginning of your learning journey, to more quickly recognize what’s going on in your code.