WhOa! What yOu need to knOw abOut big O!
I’m ashamed of that title…
As I start my career search journey following my graduation from the Flatiron School I’m realizing that there is still much to learn. I’m definitely prepared to enter the workforce as a software engineer, but there are some computer science concepts that are new to me. It has definitely given me a good case of impostor syndrome. To combat this feeling I thought I would face my fears and write blogs about all the things that are making me doubt myself. One concept in particular is Big O Notation.
Big O notation is, in essence, a way to define the efficiency of an algorithm, OR, how effective is your algorithm at solving the problem you are trying to solve in terms of time and space? The reason I find this topic so daunting is because all the technical and mathematical jargon when looking up definitions and explanations. With this in mind, I want to discuss real world situations from my life to showcase a few common time complexity solutions.
For example, as a New York based actor for the last 10 years, I have had to go through many audition processes. One common way to audition is what is known as an open call. Basically, anyone can come and sign up for an audition time on a list for an appointment slot later in the day. Now, if you are the audition monitor in charge of giving everyone a number, like at a dance call, you have the job of finding each auditionees number that correlates to their name. If everyone signed up throughout the day, then you just have a long unordered list of 500 people that you need to find the most efficient way to give them their number.
Your first instinct may be to search through the entire pile of names to find the correct number for the person at the table. This would definitely be a valid solution, albeit time consuming and extremely inefficient and you probably will never be asked to be an audition monitor again because of the amount of time you have wasted. Another solution could be to put the names in alphabetical order by last name and spread them across your table to find them faster. This will definitely save you time, but it will take up more space on your table. This is why Big O notation exists. We are able to measure the time a task takes and the amount of space it takes, so we can determine what the ‘best’ solution is to fit our particular needs.
O(1) — Constant
This measurement of time complexity signifies that no matter the size of the input the solution will take a constant amount of time.
In regards to our audition monitor, this would be setting up the holding room for the auditionees before they arrive. The room comes with 50 chairs and two tables, so no matter how many people come to audition the set up time will always stay the same, there will always be 50 chairs and two tables to set up.
Example: Finding the median value in a sorted array of numbers.
O(log n) — Logarithmic
This measurement of time complexity signifies that the solution is a logarithm of the input size. A logarithm is another way of writing an exponent. I actually never ran into logarithms before trying to understand Big O, so I found this link helpful in my understanding.
Exponent : Repeated Multiplication :: Logarithm : Repeated Division
Back to our audition monitor, this would be dividing a stack of the auditionees resumes. Divide the stack in half, look for the auditionee in one of the halves, if it’s not there, go to the other half, divide that in half, and keep repeating until you find the auditionee you are looking for. If the size of the stack increases, it may take you more time to find the auditionee, but not that much more time.
Example: Binary search.
O(n) — Linear
This measurement of time complexity signifies that the time it takes to find the solution increases as the input size increases.
Our audition monitor hates logarithmic approaches and decides that flipping through the stack from the beginning each time a new auditionee needs to be found is the best way. Our audition monitor doesn’t realize that maybe this wasn’t a terrible way to find auditionees on the day when 20 people showed up for the audition, but today 100 people showed up, so it will take them 5 times longer to find auditionees. Woof.
Examples: Finding the smallest or largest item in an unsorted array, Kadane’s algorithm, linear search
O(n²) — Quadratic
This measurement of time complexity signifies that the time it takes to find the solution increases quadratically as the input size increases.
The audition monitor has done a successful job during the initial call day. Now, it’s time for callbacks (this is when an initial audition was successful and you are called back for the next part of the audition, (initial culture interview gets you a technical interview)). Callbacks can take awhile depending on how the casting team wants to handle them. One time I was called in the morning with everyone else who was called back for multiple roles and we were all kept all day because they wanted to see everyone in various groups. Now, this can take awhile depending on how many people are called back, much like a quadratic time complexity. If casting wants to see each auditionee read as each character in a two person play with each other auditionee as each character in this two person play, the length of time it will take to see each individual pair will increase dramatically with how many people have been called back that day. And, as you can see on the chart above, this can increase the number of operations HORRIBLY.
Examples: Bubble sort; Insertion sort; Direct convolution
Why does Big O matter?
You may be asking yourself why any of this matters. If you figure out how to reverse an array or whatever you are asked to do, why do we care about Big O?
Working at a large company that handles millions of data points, a solution that runs faster or a solution that saves memory can save a company time and, more importantly to the company, MONEY, MOOLA, DINERO, CASH BABY!
As for you, the truth of it is, sometimes it doesn’t really matter. You’re right. We are here to solve problems and if you solve the problem you’ve done your job. BUT, it does come up in interviews. Knowing this is important to having a vocabulary on how well your code performs. If your code isn’t running as fast as you like, Big O can push you to identify parts of your code that can potentially be improved. And, for me, the goal is always prettier, more efficient code.
Big O notation can be pretty daunting at first if you aren’t familiar with it, but in short, it is just a way to measure the efficiency of your algorithm in regards to space and time.
Happy Coding!
