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 n² 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:

• You are allowed to buy land only in square lots.
• These lots have to be in fixed units i.e. the square lots can have a side of 1 yard or 2 yards or 3 yards.. and so on.

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.

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:

• The effort required for putting up the sign does not change at all. No matter how large your plot you still need just one sign.
• The effort required for fencing the plot increases linearly with the side of the plot. A plot which is four times as long on the side will need fencing that is four as long as well. Ten times as long on the side needs 10 times the length of fence.
• The effort required to mow the law increases as the square of the side of the plot. Your 10x10 plot needed 100 square feet to be mowed but your 40x40 now needs 1600 square feet to be mowed. A 4X increase of the side led to a 16X increase in the effort for mowing! A 10X increase led to a 100X increase!
• This is very interesting as it grows the least. A quadrupling of the side of your plot leads to just a $1 increase in property tax. A 10X increase on the side led to another dollar increase in property tax.

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

• The signage is constant time i.e. O(1).
• The fencing is linear i.e. O(n).
• The mowing is exponential i.e. O(n²).
• The growth in property tax is interesting and is best described as logarithmic i.e. O(log(n)).

Here it is summarized in table form below:

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!