What does "exponentially" mean?

We've all heard (or said) things like "such and such will improve such and such exponentially" or "if you do that, it will be exponentially better" or another variation of referring to exponential increase. Its been my experience that in almost every instance the speaker is completely wrong. Most of the people who use it, just don't know any better. They just think that exponentially means "a lot". Them I can forgive; its not their fault they never learned about orders of growth. However, I have also heard multiple people who really should know better misuse this word, including my interviewer in a recent Google interview. Someone has to put a stop to this.

Categorizing Rates of Growth

In computer science, we categorize rates of growth using asymptotic notation or "Big O Notation." Usually we use this to measure the amount that the runtime or memory usage of a program increases as the input to the program gets larger and larger. I'll go through the basics idea of what Big O means and then dig more into the details later. Basically, for any program (or at least any program for which the runtime is predictable) you could come up with a function that would tell you how many seconds or milliseconds it will take for your program to run. A lot of times it is more useful to have a function that tells you the runtime based on an input size rather than just reporting a number of seconds for a specific input size. For example, lets say we have two programs that take a list of names and put them in alphabetical order. If we just said "Program A takes 166 milliseconds to put 10 names in order and Program B takes 125 milliseconds to put 10 names in order" we would think that program B is the faster one. However, what we didn't know was that program A actually takes t=n*logBase2(n)*2+100 milliseconds to run where n is the number of names to sort and program B actually takes t=1.1*n^2+15 milliseconds to run where n is the number of names. So when n=10, B is slightly faster than A, but as n increases, A becomes much faster. If n=100,000 then program A would take about 55 minutes and program B would take about 4.2 months. By the way, both of these programs are much slower than a typical program in real life.

So its clear that its more useful to describe how a runtime grows rather than to just spit out an example of a runtime, but we really don't need quite that much detail. In fact we don't really care about the difference between t=n^2 and t=2*n^2 because you might be running one of those program on a computer that is twice as fast anyway. We need to strip out the unnecessary details and just show the basic rate at which the function grows. That's where Big O comes in. The basic (very basic) idea of Big O is that you take out an constants that are being multiplied or added and just show what type of function it is. So instead of saying the program takes n*logBase2(n)*2+100 to run, we just say it takes O(n*log(n)) and instead of 1.1*n^2+15 we just say O(n^2)

A More Formal Definition of Big O

If you felt like the section above was a good enough description of Big O for you, or you don't really care that much about the math, go ahead and skip to the next section.

The formal definition of Big O is (as I remember if from college):

Given a function f(n) and g(n), f(n) is a member of the set O(g(n)) iff
There exists a positive number C and number n₀ such that for all n > n_0, |f(n)| ≤ |g(n)|*C.

In other words, after n becomes sufficiently large, f(n) is always less than g(n) times some positive constant.

Note that according to this definition, the function f(n) = n (a pretty slowly growing function) is a member of O(n), but it is also a member of O(n^n^n^n) (a very very fast rate of growth). In general, when people ask "What is the Big O of this program" what they really mean is "What is the smallest Big O set that contains this program's runtime."

Exponential Increase

So you can probably guess by now, that to say that something increases exponentially, means that it increases at a Big O exponential rate of growth or O(B^n) (for some B > 1). So for example, if the population of your bacteria colony with respect to time is f(t) = 2^t -100t + 10000, then it is a member of O(2^t) which means your bacteria population is increasing exponentially with respect to time. Do not confuse this with polynomial increase which is O(n^e) (for some e>1). Note the difference, in exponential growth, the n is in the exponent, in polynomial growth, the n is the base being raised to some exponent. Congratulations, you should now know how to use this word properly!

Common Mistakes

So, now that you know what it means for something to increase exponentially, I'll take you through the three categories of misuses of the word starting with the most forgivable and moving towards the blatant, blaring, butcheries that make my blood boil.

First, theres the mistakes like "As the outside temperature goes up, your electricity bill goes up exponentially." This is quite clearly wrong. I don't know what the exact function relating the outside temperature and your electricity bill, but its probably roughly linear with a cap at the top once you are running your air conditioner all day. This is not anywhere close to being exponential growth, but compared to the other mistakes people make, this one is actually refreshingly close to accurate.

A worse mistake is when people say something like "If you wear the proper biking gear, the distance you can bike will increase exponentially." What on earth does that even mean? It may be true that wearing the biking gear increases the distance you can bike dramatically, but wearing the right gear is a binary variable (meaning, you can wear it, or not wear it) so what exactly is the "n" in your O(B^n)? In order for something to increase exponentially, it needs to be something you could graph on a line graph with numeric values on the x axis.


And finally, some people add a little touch on the previous mistake to push me over the edge. They continue to use a binary input value, and then they use something unquantifiable as the output value. An example is "Kraft Macaroni and Cheese tastes exponentially better than the store brand." I'm just not even going to get started on that one.

So please, go spread the word. If every person who reads this teaches 2 people a year what "exponentially" means, and each of them tells 2 more people a year and so on and so forth, then the number of people who know how to use the word properly will increase at O(2^n) or in other words, exponentially.