Small Math to Big O
Who’s afraid of the big bad O?
They say in order to conquer your fear of something, you should learn more about it. I applied this credo to my fear of flying. I started learning about how planes work, what the creepy noises I heard onboard were, and the procedures taken in cases of emergency. I didn’t totally conquer my fear, but I was much better equipped when my in-flight anxieties would kick up.
When software engineers start to study algorithms, the math-averse tend to start worrying, myself included. However, once I started to break down the reasoning and math behind Big O, it became a lot easier for me to understand. I’m going to go through a few elements behind the math and logic of big O in simple terms in order to try and demystify some of the spookiness around this subject.
The O in Big O
Let’s start by talking about the name “Big O.” Big O is a nickname for the concept of asymptotic notation, or more commonly, the order of a function. BIG WORDS SCARY, I know — we’re going to break it down. Big O basically looks at the trend a function will take according to its inputs.
If we want to visualize the order of a function, we’ll need to plot it on a graph. For those unfamiliar, plotting a function just concerns its inputs and outputs, where the x coordinate is the input and the y coordinate is the output. So when we look at the function:
f(x) = 2x“f(x)” is the answer of the function aka output when “x” is input. The right side of the equal sign is when happens to “x” when calculating the output. We can read this as, when “x” is input, “f(x)” is “x” multiplied by 2. A table for the function above looks like this:
We take those values and plot it into the graph, where the horizontal axis represents our input, “x”, and the vertical axis (usually called “y”) represents our output “f(x)”.
Fairly simple right? Now that we’ve got our functions plotted onto a graph, we can start talking about their trends. The trend is the rate of change of the function i.e. as “x” grows larger (towards infinity), “y” grows at “z” rate, where “z” is representative of the slope or steepness of the line. How do we find “z”? Simple, we take our output, and divide it by our input.
Looking at our tables, we can see that for “f(x) = x” the rate of growth is always going to be 1, and for “f(x) = 2x” the rate of growth is always going to be 2. We can then say that the functions have O(1), or constant change — because “f(x)” grows at the same rate every time “x” changes.
The Trend of Time
Now that we understand trends, we can move onto the context that big O usually concerns — the time it will take an algorithm to work as its input increases. In the last example, we looked at how the output of the function grew as its input increased. Now, instead of our vertical axis corresponding the output of the function, it will correspond to the operations needed to execute the algorithm. Let’s look at an example:
You can see from the graph that the operations needed to finish the algorithm are what dictate the amount of time that the algorithm will take. Here are some basic rules for calculating the amount of operations needed in an algorithm (thanks to Colt Steele):
- Arithmetic operations are constants: (+, -, *, /)
- Variable assignments are constants
- Accessing elements in array by index or by key in object are constants
- In a loop, the complexity is the length of the loop times the complexity of whatever happens inside the loop
Let’s apply this to a few functions:
The first function, “isit10”, has 1 operation, checking if the number is 10. If the number changes, the number of operations will NOT, so its trend is “O(1)” or constant. The same can be said for the “add1” function. The third function loops over an array, so if the length is “n”, and we multiply by the number of operations in the loop(1 operation — the multiplication), we get “1n” or simply “n”. Therefore, the function’s big O is “O(n)”, as “n” gets larger, the number of operations will get larger.
Simplifying Expressions
The functions above are fairly simple, so what happens when we get to really complicated algorithms? Here is where the ideas get simpler — literally. Since we are only concerned with the general trend of the function as it’s inputs increase, we don’t need to worry about the EXACT rates, as the differences between functions with similar trends is negligible when reaching larger input numbers.
So if a function has an “O(2n + 5)”, the 2 and 5 are constants and their effect on the rate of change will be negligible and directly proportional to the change of n. Therefore, we can simplify it down to O(n). Big O notation is more concerned with finding significant differences in time complexity like the difference between O(n) and O(n²).
One last thing…
The final rule to remember when computing time complexity of algorithms is that the order is always based on the worst-case scenario. Some algorithms have an exit condition that returns a result before executing the max number of operations, like a searching algorithm. However, we cannot predict the state of the input so we always consider the largest amount of operations the algorithm will take.
