Big O Notation
Space, Time and Optimization oh my! Look no further, this article will debunk and go through why Big O is so important to understand in programming. This blog focuses on an introductory understanding of Big O notation through Binary Search and Linear Search.
When it comes to Big O Notation, two concepts are important to understand in programming: Time and Space.
The time is takes to run an algorithm and the space/memory the algorithm takes up. The less time it takes to run the algorithm, and the less memory it takes up, the more optimal the algorithm is. Big O notation lets you understand and compare the number of operations in an algorithm and how fast that algorithm grows.
It’s important to understand algorithm run time (Big O Notation) since you will be using well known algorithms in your code. Algorithms such as Quicksort, Binary Search and Simple Search are just three examples out of the many algorithms that are key to understanding Big O. For Now, lets compare Binary Search and Simple/Linear Search.
Binary Search looks like this:
function binarySearch(array, target) {
let min = 0
let max = array.length - 1
let guess;
while (max >= min) {
guess = Math.floor((max+min)/2)
if (array[guess] === target) {
return guess
}
else if (array[guess] < target) {
min = guess + 1
} else {
max = guess - 1
}
}
return -1}
With Binary Search, you are given a target value and an array. A real world example of Binary Search is when a teacher is grading an assignment and has sorted all the students’ papers by last name. The top of the pile is A, and the bottom is Z. This means that given a target value of, for example, ‘Lebowski’, the teacher will cut the pile in half, take the top of the pile (since L is in the first half of the alphabet) and continue to cut the pile in half until the letter ‘L’ has been reached.
Binary Search cuts the array in half and continues to adjust where to look until the target value has been found.
Simple search, or linear search looks like this:
const linearSearch = (array, target) => { for(let i = 0; i < array.length; i++)
{
if (array[i] == target)
{
return i;
}
}
return -1;
}
Given a function, it has an array and a target. This algorithm states it will go through the array, one iteration at a time, and if the array iteration is the same at the target, then it will return the index.
Using the same example in Binary Search, you’re a teacher grading papers. You’re trying to find the student with the last name ‘Lebowski’. With Linear or Simple search, you will search through each paper, one at a time, from the top of the stack. See how much longer Linear Search takes than Binary Search?
In terms of Big O notation for both of these algorithms, Binary Search is a lot faster and more efficient than Linear or Simple search. Binary Search’s run time is O(log(n)) whereas Linear Search’s runtime is O(n).
Here are a couple other examples of Big O run times (from best to worst, top to bottom):
- O(log n), O(1) — constant
- O(n) — linear
- O(n log n) — linear logarithmic
- O(n²) — quadratic
- O(n³) — cubic
Big O focuses on the worst case/expected case scenario. For both of these algorithms, it is expected that their runtimes would be O(log(n)) and O(n) respectively. It is imperative for every programmer to understand as they implement their own algorithms into their own code; understanding what makes an algorithm efficient to optimize your own project’s runtime will help you debug and make your product more robust in the long run.
I hope this article was helpful for you to understand the basics of big O notation! Here are some resources I recommend to visualize, and to understand Big O a bit better:
Happy Hacking!
-Crystal
