Raghu Srinivasan

Understanding Big-O for Algorithms

Here’s a real world analogy to better understand how algorithmic complexity is most frequently described. Algorithms such as those used for sorting an array of numbers are commonly measured by how long they take to run. Time taken isn’t necessarily the only thing you care about but it’s a very important proxy for an algorithm’s efficiency. And of course, faster is better.

The measure is often referred to as the Big-O of the algorithm. Algorithms can be fast i.e. twice the amount of work still takes the same amount of time or they can be linear i.e. twice the amount work takes twice the amount of time, or exponential where twice the amount of work may take four times the amount of time and so on.

Bubble Sort for example has has a Big(O) of n2 while Merge Sort has a Big(O) of n*log(n).

To better understand this representation, with a real-world analogy, let’s go to the city of Squareville. Squareville is mostly made up of flat, grassy land. You are interested in buying land here to graze your cattle.

In Squareville, there are just two rules to buy plots. They want to keep things simple and insist on these two rules:

In other words you can’t buy a rectangular plot that is 5 yards x 10 yards. You also can’t buy a square plot of side 7.5 yards for example.

Next, once you buy the plot of land you must agree to adhere to the city rules:

  1. You are required to place a sign that says ‘Owner: So-and-so’ on one corner of the plot.
  2. You are required to fence the plot in - even if there are adjoining plots.
  3. You are required to mow the grass upon purchase.
  4. Your property tax in dollars is the same as the number of digits it takes to write your plot's square footage.
Let's say that you bought a plot that is 10x10. Then, as per the rules you are required to:
  1. Place 1 sign.
  2. Put up 40 feet of fencing (10 times 4).
  3. Mow 100 square feet of lawn (10 times 10).
  4. Pay $3 in property tax since 100 is 3 digits long.

Now let’s see what happens if you buy another plot of land that is 4 times larger i.e. 40x40. Let’s see how your obligations change:

  1. You still place only 1 sign.
  2. You now have to put up 160 feet of fencing.
  3. You now have to mow 1600 square feet of lawn.
  4. Your property tax is still $4 as 1600 is 4 digits long.

As a final example you buy a plot that is 100x100. Now here’s what you have to do:

  1. You STILL place only 1 sign.
  2. You now have to put up 400 feet of fencing.
  3. You now have to mow 10000 square feet of lawn.
  4. Your property tax is now $5.

If you pause here for a minute here’s what you’ll see about how the change in the side of your plot affects the rate at with your obligations grow:

To use Big-O terminology, here’s how each of your obligations grow:

Here it is summarized in table form below:

Side of Plot Sign (Corner) Fence (Perimeter) Mow (Area) Property Tax
10 1 40 100 3
40 1 160 1600 4
100 1 400 10000 5
Rate of growth: O(1) O(n) O(n2) O(log(n))

Clearly, it would be ideal to have algorithms that are O(1) - those that would take the same amount of time no matter how large the input. Next best would be logarithmic or O(log(n)) - those that would take more time as input grew but where the effort would grow very slowly, next would be linear where the effort was proportional to input O(n) and the worst would be exponential where the effort increased very rapidly with growth in input - O(n2).

Now you know and can handle Big(O) questions as deftly as President Obama did at Google!

email: raghu@raghusrinivasan.com