Big O for Noobs - Part III
This is part 3 of Big O for Noobs, if you’d like to read part 1, you can do so here and part 2 over here.
By now, it should be pretty clear that when iterating through a string or an array in search for something, the time complexity is O(n). O(n) is not bad, you can do worse than O(n), like O(n²). How do you get O(n²) you ask? Even if you didn’t ask, I’ll tell you. You most likely came up with a solution with a nested loop. If you find yourself coming up with a solution containing nested loops, try again. There are seldom cases when it’s unavoidable, but in most cases, when you find yourself with a nested loop, you should try again.
I remember when I was studying for the SATs a long long time ago; the Kaplan SAT prep book outlined a specific approach — the SATs always include answers to trip you up, they always place an answer that looks like an obvious choice at first glance. There are also two types of test takers — there’s someone like Karen who always fall for the traps and select the first obvious choice. And then there’s Sam, Sam always identifies the easy choice that Karen would pick and ponders a little deeper and weighs out the other choices before making his decision. What I’m getting at is, nested loops often seem to be what new programmers like to default to, the easy choice, but don’t do it. Don’t be a Karen.
Here’s an example, let’s say we want to come up with a function to identify whether 2 arrays with the same length are unique or not. What would Karen do? Most likely this:
As you might have guessed, it’s an O(n²) solution. No, Karen. Now, how would Sam do it? Perhaps like this:
Sam realizes that multiple loops are better than nested loops, his solution has a time complexity of O(2n), but since Big O doesn’t like constants, that’s O(n)! It loops through each array once, instead of looping through each element of arr1 for arr2.length times.
Sometimes we can do better than O(n), if you’re searching for data that is sorted, we can find what we’re looking for with O(logn). How? Imagine somebody asks you to guess their birthday and after each guess, they’ll let you know if it’s before or after the date you selected. The O(n) approach would be like…”Is it January 1st?”, “Is it January 2nd?”, “How about January 3rd?”. You’re right, nobody in their right mind would do that. What YOU might do is go right down the middle, “Is it July 2nd?” or “Is it June 15th?”, somewhere in that ball park. Then when he/she responds, “no, it’s earlier”, or “no, it’s later”, you have effectively eliminated half of the year. This is an implementation of how that would look like in code where if the value exists in the sorted array, the index would be returned for the value, otherwise a -1 would be returned instead:
If you copy the code, add a variable named count, increment count in the while loop, and then console.log(count) at the end, you’ll notice a pattern as you increase the size of the sorted array. What you’ll notice is that for n elements in the array, if you double n, the number of steps will roughly increase by only 1. Here, take a look at this here table if you must: https://www.logcalculator.net/log-2. This algorithm is known as Binary Search, it’s an important one to have in your toolbelt.
Well, this wraps up Big O for Noobs, there’s many more classifications out there, but as the title states, these articles are for noobs, just a primer to get started with. Anyway, I’m glad you stuck around and hope you actually learned something from it. Now, go on, fly, fly away, and write some beautiful code and remember one thing, don’t be a Karen.
***I’m sorry if your name is Karen, it wasn’t my intention to offend you***
