I recently did a technical interview assessment and I found that I needed to improve my understanding of the foundations of coding if I am going to impress a future employer. Thankfully I am privileged to have a great friend who also happens to be a computer science grad and is a great developer. Together we have been working on Javascript algorithm problems to simulate a technical interview. One of the most helpful lessons I’ve taken away so far is thinking about my code in terms of efficiency and how that relates to Big O.
If you were like me and you were asking “what is big O” here is an excerpt from Wikipedia: “In computer science, big o notation is used to classify algorithms according to how their run time or space requirements grow as the input size grows” -Quantum Computing in Complexity Theory and Theory of Computation. Mohr, 2.
Okay, so it has something to do with classifying algorithms based on how they run and their space requirements. So what is an algorithm? Let’s also look at how Wikipedia defines an algorithm: “In mathematics and computer science, an algorithm is a finite sequence of well-defined, computer-implementable instructions, typically to solve a class of problems or to perform a computation”-The Definitive Glossary of Higher Mathematical Jargon. Math Vault.
Hey cool, so in code that means when we write functions that take in data as an input in a sense we are writing an algorithm of our own. So big O is a tool we can use to determine how our effective our code is relative based on the assumption that the input size could grow. The more time it takes for the algorithm to run the less efficient the algorithm is and we want efficient algorithms. Apparently that is what all the cool coding kids who have jobs to fill want.
For instance, let’s say we needed to check a list of numbers and if there are any 0’s in the list then make the computer say “hey there’s a zero in here.” otherwise say “no zero here.” That seems simple enough, just make something that would check each number in the list(array) and if it finds a zero spit out the captain obvious text:
[1,2,0,3,4] // need to find a way to identify the 0 from this list(array)Since we are focusing on big O I won’t be going into detail over each line of code, but I’ll be sure to have more articles on each later! The following code will be in good ole Javascript: Also sidenote this function is to demonstrate big O and not meant to make sense in any real-world scenarios :
const numberList = [1,2,0,3,4]
function findTheZero(array){
for (let i=0;i < numberList.length; i++){
if (numberArray[i] !== 0){
console.log("this isn't a zero.")
}
else {
for (element of numberList) {
if (element === 0) console.log("found a zero!")
}
}
}
}findTheZero(numberList)
/// this should print in our console:
no zero here
no zero here
found a zero!
no zero here
no zero here
sweet so this function does the job. It scans through the array and if it finds a zero it says the prompt. So what the problem is and how does a big O factor into this? Well as we discussed in the beginning, big O is a tool to assess the algorithm’s run time or space requirements as the input size grows. So in our example, let’s pretend that the number list is
[1,2,3,4,5,6,7,8,9,0,10,11,12,13,14,15,16]instead of just [1,2,0,3,4]. Our console would be littered with “no zero here” until with one “found a zero!” near the middle. Also if we remember the original problem it simply stated if there are any zeros… so once we find the zero (assuming there is one)our job is done. Otherwise, just say “no zero here”. We don’t need to keep scanning the array if we find a zero. Also, we don’t need to say “no zero here” here each time we check a number. How about instead we try something different:
cconst numberList = [1,2,0,3,4]const aSecondNumberList = [1,2,3,4,5]function findTheZero(array){const lookForZero = array.find(element => element === 0) if (lookForZero === 0) console.log("hey there is a zero here") else console.log("no zero here")}findTheZero(numberList)// expected output is:// hey there's a zero in herefindTheZero(aSecondNumberList)// expected output is:// no zero here
What changed this time around? Well for starters there isn’t any scary looking math like things in it such as the two for loops. Instead, we are using a Javascript method called .find() which does what this for loop did:
for ( let i=0; i<numberArray.length; i++)but .find() is a better fit for our problem. The .find() scans the array left to right and when it finds what is in the parentheses it returns true or essentially says “I found what you were searching for and now I’m done looking” (I like to personify my javascript methods). This makes our function more efficient since we don’t have to scan through the entire array and then determine if there is a zero in the array by looking through all of the console logs. More importantly, we are only scanning the array once in this new example. Whereas in our first example we had 2 for loops:
for ( let i=0; i<numberArray.length; i++)andfor (element of numberArray)
this is significantly more taxing for a computer to run since it has to go through the same array twice, one for each loop.
It may not seem significant, but the data we work with can be very big. Like very very big, instead of 20 numbers maybe the array is 2 billion numbers. This is when big o notation is a great tool to see how efficient our function is.
In our first example, we had our for loops looping through the entire array and making a console log every time it scanned a number. Whereas in the second example we also looped once through the array and if we found the zero our while scanning our function stops. Big O would notate the two functions differently with one being more efficient than the other.
const twoBillionNumbers = [1,2,3,4,0,5,6...2000000000]can you imagine if we were using the first function vs the second? We would be saving literally billions just by stopping the function when we found our value.
A breakdown of the different notations in big O will be for another article. It is something I too am still learning, but if you’re like me I would encourage anyone who is interested more in big O to check out this great video series by Garrett Halstein
Big O is something that will take time to understand and learn, but by beginning to think about how effective your functions will improve your understanding of coding overall.
