Big-O notation is a method of specifying the worst-case performance of an algorithm as the size of the problem grows. Big-O notation is important for understanding how algorithms scale and for comparing the relative performance of two algorithms. An algorithm is a set of specific steps or instructions for solving a problem.
Years ago, a ferocious wizards’ war raged across the land. Initially sparked by a disagreement over the correct pronunciation of the word “elementary,” the conflict quickly escalated. The battles lasted months. Neither side could gain an upper hand. The strength of the two sides was almost perfectly matched—until a computational theorist shifted the balance of power forever.
Clare O’Connell was not a wizard, but rather an accountant. She worked in the Bureau of Farm Animal Accounting: Large Mammal Division, where she spent her days tracking the kingdom’s cows, horses, sheep, and pigs. It wasn’t an exciting job, but it left her plenty of time to pursue other interests, such as computational theory. In fact, in only three years after her arrival, Clare had assembled the kingdom’s greatest collection of computational theorists within the bureau.
Clare had never taken any notice of the war until she was caught in the middle of a battle. Wizards’ wars tended to be well separated from daily civilian life. The wizards would bicker and fight amongst themselves, but would rarely resort to any spell that had an impact on the general population. In fact, they avoided spells that could cause any actual physical harm altogether.
During one early May morning, Clare was accidentally caught in the crossfire. She had been leaving the baker’s shop when a stray spell turned her bread into a frog. The true target, a loaf of pumpernickel held by the wizard behind her, remained unscathed and quite edible. Unfortunately, the same could not be said for Clare’s bread, which promptly hopped out of her hand and down the street. Clare was furious.
That morning, Clare resolved to break the stalemate and end the war for good. Since she didn’t have a strong opinion on the pronunciation of “elementary,” she chose to meet with the commander of the closest faction. During a three-hour meeting, she grilled him about the war’s progress. In the process, she learned how wizards thought about their spells. The interview ended with one unmistakable conclusion: wizards knew nothing about computational complexity. Years of casting spells had made them lazy and inefficient.
Clare knew that the first side to relearn the importance of computational complexity would win the war. So, she called together all of the wizards from the closest faction for a tutorial at the local pub.
“Your problem is that your techniques are inefficient,” she began.
The wizards mumbled in protest. How dare this accountant lecture them on the art of casting spells? They threatened to transform her drink, a well-made and perfectly heated mug of tea, into oatmeal.
“But there’s a solution!” Clare continued. “There’s a new technique, called Big-O notation, that will shift the tides. This notation tells you how a spell performs as the size of the battle increases, allowing you to know which spell is most efficient. You simply ask: how many steps does it take to cast a spell when facing N different enemies? Then you strip out all the constant factors and focus on just the parts that grow the fastest.”
“For example,” Clare continued, “if a spell takes three steps to cast, regardless of the number of enemies, then it’s an O(1) spell—constant cost. In contrast, if you need a single step for each pair of enemies then the cost is O(N^2)—quadratic cost. In a large battle, you want spells that will scale well.”
The wizards grumbled in protest.
“That would never work.”
“It simplifies the problem too much.”
“This accountant is crazy!”
Clare was unfazed. “What’s your favorite spell?” she asked a wizard in the front row.
He turned red at being singled out and mumbled, “The Spell of Pairwise Protection.”
“Which does … ?” prompted Clare.
“Well, if you cast it on an enemy and a friend, the friend is protected from that enemy for a full five minutes.”
“How long does it take to cast?”
“Two seconds. It’s a fast spell.”
“But how well does it scale?” asked Clare.
“Scale?” asked the wizard.
“I mean: how does the performance change as you add more and more people to the battle?” explained Clare. “The performance of this spell depends on how many people are in the battle.”
The wizard looked back blankly.
Clare sighed. “When you’re in a large battle, you need to understand how the cost of using a spell increases as the number of people in the battle increases. Let’s take the Spell of Things Smelling Like Fish. You cast it once for each enemy in the battle and they smell rotting fish for the next half an hour. One step for each enemy, so it’s an O(N) spell. It scales linearly with the number of enemies.”
“In contrast,” Clare continued, “the Spell of Pairwise Protection requires you to cast it on each pair of friends and enemies. If there are N enemies and M friends, you need to cast it M ? N times—one step for each pair. So the cost is O(M ? N). If you have a lot of friends, that’s going to take a while.”
“Good thing Henry doesn’t have many friends,” someone joked from the back row. A few muffled laughs followed. Clare ignored the comment.
“The Spell of Things Smelling Like Fish takes 15 seconds to cast,” objected a wizard in the back row. “Your Big-O notation doesn’t capture that!”
“You’re right,” admitted Clare. “Big-O notation is only used to compare how spells scale as the size of the battle scales. This is where your strategy is lacking. You’re still accustomed to the simpler world of dueling, where the number of enemies is always one. You focus too much on the constant factors.”
Clare continued, “At some size of battle, an O(N^2) spell will take much longer than an O(N) spell. At some point, the constant factors don’t matter anymore. That’s the value of Big-O notation.”
The same wizard went back on the offensive. “Are you telling me that it’s better to cast the Spell of Loud Techno Music, which takes one hour and impacts all enemies, than the Spell of Temporary Elevator Music, which takes one minute but impacts only one enemy? It would seem that that is what your Big-O notation would recommend.”
“Yes,” said Clare. “If there are more than 60 enemies, the Spell of Loud Techno Music is more efficient the Spell of Temporary Elevator Music.”
The wizard was stunned. He repeated the math over and over in his head to check her answer. Clare knew that he would eventually come to the same result. Accountants were notoriously good with numbers.
“What about the Spell of Love Triangles? That takes only one second to cast and the results are so much fun to watch,” argued another wizard.
“You need to cast it on all triplets of people, so it’s O(N^3). If you have twenty opponents, that’s 20 * 20 * 20 = 8000 seconds! That’s over two hours!”
The wizards gasped in unison. They had never thought about it like that before.
“Consider the Spell of Uncomfortably Long Toenails,” suggested Clare. “This spell fell out of favor a few years ago, because it needs 120 seconds of preparation before casting it for the first time each day. It wouldn’t work well in duels. However, after you perform that preparation once, it only takes five seconds per enemy. So the spell takes 120 + 5 ? N seconds for N people. Big-O notation strips out all those constant factors and simply asks, ‘What happens to the cost as N gets really large?’ In this case, the answer is: the Spell of Uncomfortably Long Toenails scales linearly. It’s an O(N) algorithm, because as N grows that’s the term that dominates.”
By the end of the night, Clare had convinced all of the wizards in the room to pay attention to the Big-O cost of the spells they used. It was a radical shift from the way they had always looked at their spells, focusing solely on the cost for casting it once. The Spell of Broken Command Chains, which had to be cast on all possible orderings of opponents—O(N!)—immediately fell out of favor. Spells that scaled well became new standards.
Tired but satisfied, Clare went home for the night. On her way home, she stopped at the baker’s again for a loaf of fresh bread. While standing behind the counter, she noticed the baker using an O(N^3) algorithm to make rolls. With a put-upon sigh, she interrupted the work. “You know that that isn’t the most efficient way to make rolls …” she began.
If you liked this story, the author has written many more collected in several books linked below, including in July 2016 Search: A Tale of Algorithms, Computation, and Conspiracy. This story is reprinted with permission of the author, Jeremy Kubica.
Learn More
Big-O Notation
https://en.wikipedia.org/wiki/Big_O_notation
https://justin.abrah.ms/computer-science/big-o-notation-explained.html
http://bigocheatsheet.com/
Search: A Tale of Algorithms, Computation, and Conspiracy
https://www.nostarch.com/searchtale
Computational Fairy Tales
http://computationaltales.blogspot.com
http://computationaltales.blogspot.com/p/book.html
https://twitter.com/compfairytales
Search: A Tale of Algorithms, Computation, and Conspiracy
To be released July 2016, you can order early and get a discount.
https://www.nostarch.com/searchtale
Best Practices of Spell Design
http://www.amazon.com/Practices-Spell-Design-Jeremy-Kubica/dp/1481921916
Computational Fairy Tales
http://www.amazon.com/Computational-Fairy-Tales-Jeremy-Kubica/dp/1477550291/
