This content originally appeared on DEV Community and was authored by Ashley D
After our bootcamp, we were challenged to learn data structures, and I noticed a gap: a lot of online resources dive deep right into the math behind calculating Big O Notation through data, which can be intimidating for beginners. Instead, I want to make a beginner-friendly approach using something we all can relate to: laundry day.
Table of Contents
- The Big O Graph 📉
-
What Do Those Lines Mean? 📊
-
Not Good
- Quadratic Time - O(n^2)
- Linearithmic Time - O(n-log-n
-
Okay
- Linear Time - O(n)
-
Good
- Logarithmic Time - O(log n)
- Constant Time - O(1)
-
Not Good
The Big O Graph 📉
Image Credit: Big O Cheat Sheet
Here’s the typical Big O graph you see in many articles and videos. Let's break it down real quick:
- Algorithm: A set of systematic instructions for solving a problem, like directions from your home to the grocery store for chips or the movie theater.
- Operations: How many steps your algorithm will perform relative to the number of elements.
- The graph's x-axis shows the number of elements to process, and the y-axis shows the number of operations necessary to process each element. If time increases too much with more elements, that's not optimal. Imagine customers having to wait longer, or an app crashing because it's taking too long to load something. But if more elements take proportionally less time (i.e. less operations) to process as the data size grows, that's good—it means we're being efficient!
What Do Those Lines Mean? 📊
Let's make this relatable. Imagine it's laundry day.... We've all been there, right?
Below you will see laundry day analogies for the various big 0 notations, in regards to time complexity.
(I’ve also grouped them by okay, good and not good for their efficiency)
Not Good 🙁
Quadratic Time - O(n^2) 😓
Imagine you are done with laundry day. You need to find the sock pairs, however the socks aren't paired up yet. To do your laundry quadratic style- you need to iterate over all laundry items, making every combination of 'two-item pairs'. Some of these will be a pair of a shirt and pants, some will be a shirt with one sock, and some will be two socks. Clearly lots of 'pairs' are needless, but this would succeed in finding the perfect pair of socks eventually.
This is similar to the idea of a nested loop in code.
for (int i = 0; i < socks.length; i++) {
for (int j = i + 1; j < socks.length; j++) {
if (socks[i] == socks [j]) {
// Found a pair of socks
}
}
}
Linearithmic Time - O(n log n) 🪵
This is like “fancy” sorting—dividing or grouping the problem to avoid repeated steps. Imagine you need to organize all your clothes after laundry day.
First, you separate your clothes into different categories: socks, shirts, pants, etc. This initial division helps reduce the problem size (or how many clothes you have to sort through). Next, within each category, you sort the items by color. For example, for socks, you put all the purple socks together, then the green socks, and so on. Finally, within each color group, you sort by size It avoids touching each clothing repeatedly as we saw in the quadratic example above.
As you can see in the example below, once the clothes are divided into smaller groups, sorting within each category is much faster. Since each category has fewer items, you avoid repeatedly handling the entire pile- meaning operations (sorts) to go through the smaller pile.
Okay 🤔
Linear Time - O(n) 🔍
This is like opening each drawer to find your socks. The number of operations it takes grows in proportion to the number of drawers.In this case, one operation is opening each drawer to check inside.
- If you have 2 drawers, it will take 2 operations. Let's pretend it takes you 5 seconds to open each drawer and look, so that's 10 seconds.
- If you have 10 drawers, it will take you 50 seconds (10*5).
- Now, imagine if you had 10,000 drawers—it would take you 50,000 seconds or roughly 13.9 hours! Would you want to open each of those 10,000 drawers?
In code, this is like a for loop iterating through each element (drawer) to perform an operation:
for (int i = 0; i < drawers.length; i++) {
// Check each drawer
}
Good 🌟
Logarithmic Time - O(log n) 🔍🕵️♂️
Imagine you know your drawers are alphabetically sorted by clothing type. When searching for socks, you start in the middle... If you find pants, you realize you've opened too high, so you continue searching in the lower drawers. This means you don’t have to open all the drawers above the pants.
This method allows you to skip entire sections of drawers with each search, reducing the number of drawers you need to open to find your sock. Thus, it's more efficient and takes less time to locate your item compared to searching through every drawer linearly.
This is similar to a binary search.
int binarySearch(int[] drawers, int targetSock) {
int left = 0;
int right = drawers.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (drawers[mid] == targetSock) {
return mid; // Found the target at index mid
} else if (drawers[mid] < targetSock) {
left = mid + 1; // Continue searching right (upper) half
} else {
right = mid - 1; // Continue searching left (lower) half
}
}
return -1; // targetSock not found
}
Constant Time - O(1) 🚀
This is like having your drawers labeled on the outside so know exactly where your socks are. It doesn’t matter how many drawers you have; you only need one operation where you open one drawer because you “know” where the socks are so you only have to open one drawer.
Think of a HashMap where you can quickly find an item by key. The key would be the label on the outside of the drawer (which would say socks), so you know to open up drawer 3. Regardless of how many drawers you have- you know it’s always going to be drawer 3.
HashMap<String, String> drawerMap = new HashMap<>();
drawerMap.put("favoriteSocks", "Drawer 3");
String socks = drawerMap.get("favoriteSocks"); // Instant lookup
This content originally appeared on DEV Community and was authored by Ashley D
Ashley D | Sciencx (2024-07-18T05:02:08+00:00) big 0 notation: laundry day. Retrieved from https://www.scien.cx/2024/07/18/big-0-notation-laundry-day/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.