Understanding Big-O Notation and the Wizards' War

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 in understanding how algorithms scale and for comparing the relative performance of two algorithms.

Years ago, a ferocious wizards' war raged across the land. Initially sparked by a disagreement over the correct pronunciation of the word “elementary”, things quickly escalated. The battles lasted months, as the two sides fought to break the stalemate. 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. Her formal training was as 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 was not an exciting job, but it left her plenty of time to pursue other interests.

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. But during one early May morning, Clare had been 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. So, she met 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 faction for a tutorial at the local pub.

"Your problem," she began. "Is that your techniques are inefficient."

The wizards mumbled in protest. How dare this accountant lecture them on the art of casting spells? They threatened to transform her drink into oatmeal.

"But there is a solution!" Clare continued. "There is a new technique, called Big-O notation, that will shift the tides. This notation tells you how a spell scales as the size of the battle increases, allowing you to know which spell is most efficient. You simply ask: how many steps you need 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 3 steps to cast, regardless of the number of enemies, then it is 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 is simplifying the problem too much." "This accountant is crazy."

Clare was unfazed. "What is your favorite spell?" Clare 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 is a fast spell."

"But it also depends on how many people are in the battle. Doesn't it?" Clare pointed out. The wizard looked back blankly.

Clare sighed. "When you are 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 is a 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. So the cost is O(M*N). If you have a lot of friends, that is going to take a while."

"Good thing Henry does not 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 does not capture that!"

"You are correct," 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 are still accustomed to the simpler world of dueling, where the number of enemies is always one. You focus too much on the constant factors."

"Let me assure you," Clare continued, "at some size of battle an O(N^2) spell will always take much much longer than an O(N) spell. At some point the constant factors just do not matter anymore. That is the value of Big-O notation."

The same wizard went back on the offensive. "Are you telling me that it is 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 emery? 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. She was correct.

"What about the spell of Love Triangles? That takes only 1 second to cast," argued another wizard.

"You need to cast it on ALL triplets of people. So it is O(N^3). If you have twenty opponents, that is 20*20*20 = 8000 seconds! That is over two hours!"

The wizards gasped in unison. They had never though 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 a 120 second preparation before casting it for the first time each day. It would not work well in duels. However, once you perform that preparation once, it only takes 5 seconds an 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 is an O(N) algorithm, because as N grows that is 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 that they were using. It was a radical shift from the way they had always looked at their spells, where they had focused solely on the cost for each time they cast it. Spells 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 is not the most efficient way to make rolls…" she began.

--------------

For more on Big-O notation, see Paul the Pessimist and the Log-N Realization.