I recently started an MSc in Computer Science and AI. With a pleasant introduction to JAVA and some basic programming tasks, it quickly took a devastating turn into ‘basic’ data structures and algorithms. Now when I say ‘basic’, it’s definitely not. As someone very unfamiliar with math, the ‘basic’ symbols and formula quickly started to confuse. As such, I’m in the process of doing my own mini-course on algebra, calculus and today Big O Notation. My hope is that as I transcribe my own process, it will help me to understand it. If it also helps you, then win: win.
If you’re a student like me and trying to wrap your head around Big O notation. The way it works and why it’s ESSENTIAL to know and understand, then you’re in the right place! Let’s take a look in a fun and beginner-friendly way:
Imagine you’re at a party, and the host just announced a dance competition. There are different moves, and each has its unique degree of difficulty. You and your friends want to find out which dance move is the most complex. In the world of computer science, we would use Big O notation to represent the complexity of these dance moves, just like we do with algorithms.
If you google for a Big O definition, you get this:
“Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. It is a member of a family of notations invented by Paul Bachmann, Edmund Landau, and others, collectively called Bachmann–Landau notation or asymptotic notation.”— Wikipedia’s definition of Big O notation
What does that even mean? FreeCodeCamp does a better job of simplifying and explains that ‘ Big O notation describes the complexity of your code using algebraic terms’.
Much better.
The Dance of Algorithms
An algorithm is a series of steps used to solve a problem or perform a task. In computer science, we measure the efficiency of algorithms by looking at their time complexity, which is just a fancy term for the amount of time an algorithm takes to run.
Now, let’s get back to our dance party. Each dance move is like an algorithm, and the time it takes to perform the move is the algorithm’s time complexity. Just like dancers aim for smooth and efficient moves, we want our algorithms to be efficient too. And that’s where Big O notation comes in!
Big O notation is a way to express the upper bound (or worst-case scenario) of an algorithm’s time complexity. In other words, it helps us understand the maximum number of steps an algorithm might take as the size of its input increases.
Let’s say we have a simple dance move called “The Clap” that takes one step to perform. No matter how many people are dancing, it will always take one step to perform The Clap. In this case, we’d say the time complexity is O(1) because it’s constant and doesn’t change with the number of dancers.
But what if we have a more complex move, like “The Conga Line,” where everyone lines up and follows the leader? The time it takes to perform The Conga Line depends on the number of dancers. If there are n dancers, the time complexity is O(n) because it increases linearly with the number of dancers.
Exploring Other Big O Notations
There are many types of Big O notations, each representing different time complexities. Let’s look at a few more using our dance party analogy:
- O(log n): Imagine a move called “The Binary Dance,” where you have to divide the dance floor in half, then in half again, and so on, until you find the one spot where you can stand. As the number of dancers increases, the number of steps only grows logarithmically.
- O(n^2): Picture “The Partner Swap,” where each dancer has to dance with every other dancer. The number of dance pairs grows quadratically with the number of dancers. The more people at the party, the more time it takes to complete the move!
- O(2^n): Let’s say there’s a move called “The Exponential Hustle,” where each dancer has to teach the move to two other dancers, who then teach it to two more dancers, and so on. The number of steps to complete this dance move increases exponentially with the number of dancers.
The Big O Cheatsheat has some nice explanations and a more in-depth look at all the possibilities:
Understanding Big O notation is essential because it helps us choose the most efficient algorithm for a particular task. It’s like choosing the best dance move for the song that’s playing – you don’t want to pick a move that takes too long or is too complicated when there’s a simpler and more point-efficient version.
Remember, the goal is to choose the right algorithm (or dance move) for the task at hand, and knowing the time complexity can make all the difference.
I hope this helps.
T3B
