Why doesn’t Ed Sheeran have an album called “Algo-Rhythms” yet?
I mean, come on. With his first few albums being titled “+”, “×”, and “÷”, this potential math/music pun is staring us all right in the face. Maybe we can at least hope for a “Loga-Rhythms” at some point?? If not, serious missed opportunities, dude!
ANYWAY- So what’s the deal with Algorithms? More specifically, if you are new to the realm of Computer Science / Programming, why should you care about this buzzword? Great question.
The term ‘algorithm’ may sound a bit fancy to the unfamiliar, but the word really just means some sort of set of repeatable steps. Consider what you do every time you whip up a classic Peanut-Better, Jelly, and Pickles sandwich (Stop making that face. On my honor, it is the most delish sandwich I have ever had — dill pickles only please). You take out the bread, spread some chunky PB on each slice (this way the jelly doesn’t make the bread soggy), spread some jelly on top of the peanut butter on one face (just one face- we’re watching our sugar), cover one face with some dill pickle slices, and then slap ‘em together. Would you like another? Probably, it’s delicious. So what do you do next? The same thing, all over again.
Wait, what? So, making a sandwich is an algorithm? Yes. As is almost any remotely routine activity that you do. Taking a shower? Take off your clothes, turn on the water, step inside, soap up, rinse off, and dry. And then lather, rinse, repeat next time you take another shower. If you do the same steps each time to get you from the start of the process to the end result, that’s an algorithm.
++++
So, if we understand what algorithms are, then identifying them isn’t too tricky. They’re pretty much everywhere. Identifying algorithms isn’t our concern here. Rather, we care about comparing them and their respective efficiencies. Not every algorithm that accomplishes the same end result is equal.
Say I teach a 6-year-old to make the same PBJP, but she doesn’t quite remember the exact way I did it. So she takes out three slices of bread, then puts one back, then spreads peanut butter on one of the slices, then rinses the knife off (lots of pb down the sink drain), then uses the knife to spread some jelly, then remembers about the peanut butter on the other side, so she gets a new knife and spreads some more peanut butter, slaps it together, but then realizes she forgot the pickles, so carefully pulls the sandwich apart, fishes out some pickles with her unwashed fingers, puts ‘em on the sandwich, and then delicately puts the faces together, quite proud of herself. In the end of this process, she and I end up with the same result. But one of these processes was much smoother, cleaner, and with much less wasted time (and peanut butter). The other process was far less efficient, though admittedly much cuter.
Want to read this story later? Save it in Journal.
When it comes to making one sandwich for lunchtime, it’s not really a big deal whether we make it with my algorithm or her algorithm. I mean what’s an extra 2–3 minutes and a little sponge over the counter? But now suppose we’re catering for a party of 100, 1000, or 100000 people, and they all want PBJPs (who could blame them?). Now it makes quite a difference which way we make them. We need to make sure that our catering staff makes these sandwiches in the most efficient way possible. An extra 2 minutes per sandwich for 1000 sandwiches is an extra 33 hours. We can’t afford that time.
The same thing applies to algorithms in programming. A little algorithmic difference here and there for an array of 10 or 20 elements? No big deal. But deal with hundreds of thousands of data points? We don’t have time and memory to spare.
××××××
Because of this concern, we have ways of classifying algorithms based on their efficiencies, making them easier to compare. Two of the most common of these ways are known as “Big-O” and “Big-Theta” notations. These notations take any algorithm and classify it by comparing it to simple mathematical “parent functions”, based on its number of iterations and growth rate. What do we mean by growth rate? Well, just like in the PBJP sandwich example, differences in algorithms don’t matter much with small data, but as the size of our input grows, the time taken by our algorithm will grow as well. So when we say that an algorithm is of class O(n²) for example, we mean that for an input of size n, the algorithm will do at most n² iterations. If we have an array of 100 elements, the algorithm going through the array could run up to 10000 times. With 1000 elements, we’ve grown to possibly one million iterations of our algorithm.
You might notice I just used the terms “at most” and “up to”. This is because “Big-O” notation cares about the upper bounds of our algorithmic functions. Almost like a “ceiling function” of sorts. Saying that an algorithm is in O(f(n)) is like saying “for an input of size n, this algorithm will never run more than f(n) times.” It may certainly run quicker from time to time, but we expect it to never exceed the function in the parenthesis, aside from a constant multiple.
Big-Theta is a lot like that too, except a bit stricter. With Big-O notation, if an algorithm is, say, O(n⁵), then it’s also O(n⁶), O(n⁷), O(n⁹), O(n³⁰), etc. If it will never exceed n⁵, then it certainly shouldn’t exceed anything bigger, like n⁶ or n³⁰ either. So while Big-O notation is very good, it can at times be a bit more vague. Sometimes it’s more helpful to have something more specific (we might say “something with a tighter bound”), and for that we can use Big-Theta notation. Big-O notation cares only about an upper bound, but Big-Theta notation cares about upper and lower bounds. So while an algorithm might be able to be both O(n⁷) and O(n¹⁰ ), it cannot be both Θ(n⁷) and Θ(n¹⁰) — only one or the other.
An algorithm that is Θ(f(n)) is always also O(f(n)), but the opposite is not necessarily true. If you tell me you ate a PBJP (specific), I know for certain that you ate a Delicious Sandwich. But if you just tell me you ate a Delicious Sandwich (less specific), I don’t know for sure whether or not you ate a PBJP.
÷÷÷÷÷÷÷÷
Here are just a few quick examples of these notations, to give you an idea:
- Accessing a particular element in an array is Θ(1), because it will always take the same (constant) amount of time to find it, no matter what the length of the array is.
- An ordinary for-loop that runs through every element in an array of length n is Θ(n).
- A nested for-loop that runs through every element in an array of length n against all other elements in that array is Θ(n²), because it runs n times for each of n times.
- A nested for-loop running every element of one n-length array against every element of an m-length array is Θ(mn). This can also be considered O(n²) or O(m²), depending whether n or m is bigger, respectively.
- A function that takes in an n-length array and, for each element, calls itself recursively with the same array minus one element, will be Θ(n!). This is pretty bad, because although factorials look charismatic, their growth rates are as well. However, in some situations, factorial time might be the best you can manage.
Certainly, the quicker we can accomplish a task, the better. That means minimizing the functions inside of O(f(n)) and Θ(f(n)) whenever possible. To do so, we have to work on writing efficient algorithms, and refining them to make them even more efficient.
To write a computer algorithm in general makes a decent programmer. If you’re there, great job! But to optimize your algorithms takes you to the next level and helps you to be ready not just to find solutions to your problems, but to find even better solutions to even harder problems.
📝 Save this story in Journal.
