I am currently enrolled in WGU, a fully online college where I am getting a Computer Science Bachelor’s degree. To help solidify the information I learn there, I am going to reiterate things here so that I can express things in the form of teaching - a tool others can use, if not a way to find my own shortcomings or areas I need to improve upon.
Recently, I finished a section of a Discrete Mathematics II course on Algorithms. This section focused on the structure of what an algorithm is, asymptotic growth of functions, analysis of algorithms, and advanced analysis of algorithms. Generally, the topics discussed in this section are not complicated - but can seem that way prior to the reading.
What is an Algorithm?
First, an algorithm is a set of instructions - and despite the preconceptions we might have, they are not strictly for computers. In fact, every time you’ve been taught a specific way to solve a math question has been the translation of an algorithm directly for you to use. From expanding factors, to quickly finding derivatives, to graphing a polynomial - it is through algorithms that we teach each other how to solve things.
It could also be said that even things outside of math could fall into the realm of algorithms - but this is a bit more of a stretch. Changing the oil on your car, for example, could be seen as a stepped process in which you achieve a predictable and known result - following back to the idea of algorithms as exactly that. In terms of math, however, algorithms are a clinically precise way to solve clinically precise questions.
These questions and processes for solving them are not always what is considered the best way either. A simple solution for me or for you could be extremely fast, but to implement that into something a computer can do might not be as simple. This is because there is a hard translation barrier between how we can process things (biologically, massively parallel, fast recall) versus how a computer might (binary, sequentially, deterministically). Often, an algorithm that is perfect for a computer may seem completely useless to a person - and that is often the case in computer based algorithms.
Algorithms in Discrete Mathematics
Discrete Mathematics works on the logical steps involved in algorithms, but it should be noted that algorithms extend far beyond the constraints Discrete Mathematics might otherwise put on the idea. If-else statements, for loops, while loops, logical comparisons, each of these are discrete steps in a process that feeds directly into the foundations and strengths of Discrete Mathematics itself. Take a step, do or check its parameters, and continue to the next step. These are the building blocks of computer algorithms that we use every single day - from simple sort algorithms, to search algorithms, to much more complicated neural net training in massive data centers.
Big O Notation
The key detail we need to remember about these algorithms then, as they scale in purpose and intent, is how their asymptotic growth changes over time. This is where the idea of ‘Big O’ notation comes in - a measurement of how time or space complexity builds on an algorithm, and can determine when and where it is most useful. A small side note, Big ‘O’ was chosen by Paul Bachmann to stand for Ordnung, meaning the order of approximation.
Big O notation has a few known outcomes that every algorithm can be reduced down to. This is O(1), O(log(n)), O(n), O(nlog(n)), O(n^x), O(x^n) and so on. These are growth curves for time or space complexity that determine how efficient an algorithm is in certain contexts. These are ranked in order of their growth, seen by plotting them on a graph - where you would see O(1) failing to grow no matter the size of the set, all the way up to O(n^x) where x can be any number that shows polynomial growth, often seen in nested loops or deep stacks.
Sometimes, you will be unable to create an algorithm that is able to do something in O(1) time (constant time), because of data constraints or sorting criteria. It is then much better to look for the minimal complexity you can implement. Some may have a split complexity, from O(n) for sets of less than 5, and O(log(n) for sets greater than 5 as an example - in which case, you know you must only apply this algorithm in certain instances, or you leave computational speed on the table.
Analyzing Your Code
To see what your program runs in, you can follow a few simple steps - know what basic calls require, and what they respond with. Setting a variable (int x = 8 for example) is a known constant, it will only ever cost in constant time, assuming you are not setting its value from a function call or other criteria. A loop is almost always n time, where the deeper the loop goes can cause n^x time complexity. Log(n) is where your set is cut geometrically, or more easily understood as the opposite of exponential growth. If I have a function that must find something in an ordered set, I could check every single element for O(n) time, or I could check it by a binary search given that it is already ordered - seeing if x is greater or lesser than the middle, then repeating that until I find the known value I wanted, creating O(log(n)) time.
Combining Complexities
You can also add these together - but it should be said that while multiple O(1) instances seem like they might add up to O(5), that is a more critical examination of process requirements than what Big O approximates. Instead, O(1) steps are put together to only ever be their minimum - that being O(1). The same for the other forms of Big O notation. When added to each other, however, more complexity can shine through. If you were to add O(1) with O(n), then you would get O(1n), which comes back to O(n) by simplification. In the same way, if I have a loop that iterates for a few elements, but it does so through a binary search algorithm, it is able to run in O(n) for the loop, and O(log(n)) for the search, but then how do they combine?
The answer is as simple as previous - the notation will combine as O(n*log(n)), which is in itself a simplified approximation of its asymptotic growth.
The Limits of Big O
That being said, there are weaknesses to Big O notation that many might sweep under the rug when its convenient. For example, Big O doesn’t take into consideration hardware limitations, cache behavior, constant factors, or even problems that don’t have known polynomial-time solutions. Big O is in itself a cudgel for a world that often requires a scalpel - but that doesn’t mean it doesn’t have its uses. Applying Big O requires you to know these limitations, so you don’t assume your code is strictly O(nlog(n)) when in a real production environment, it suddenly explodes into O(x^n).
Real-world performance is often an entirely different animal than what Big O notation often spells out, and it is our job as Computer Scientists to understand when and where to apply that cudgel.
Conclusion
Put together, we can see that Big O Notation is a powerful tool that is the underlying science of how computation works - and shows a clear example of how smaller foundations can often compound into much more complex topics. What may start out as a simple test on sorting and its costs, could grow into the very underlying nature of how large databases are built around something as simple as understanding O(nlog(n)). That is taking the powerful currents that understanding the math behind computers can take you into far higher orders of work where you might never see the true connection.