What is Big O?
Big O Notation (the O stands for Order) is the measurement of how long it an algorithm to run (time complexity) or how much memory it used by that algorithm (space complexity). The purpose of Big O is to express the worse, average, and best running time of an algorithm.
- How fast the runtime grows: It is hard to determine the exact runtime of an algorithm. It all depends on the speed of the computer processor.
- Input (O(n)): To measure speed of an algorithm , we would be using seconds and minutes. But with measuring how quickly the runtime grows in computer, we would be using the size of the input, which we can call
“n”.That way with N, we can start saying things like “the order of the size of the input (O(n)) or “the order of the square of the size of the input (O(n²)).
Big O Notation Cheat Sheet
Constant time or O(1)
Constant time means that it take a consist time to run an algorithm, without worrying about the input size.
A great example would be bookmarks, bookmarks allows readers to find the last page that the reader has left off. No matter how many pages the books has, the bookmark will bring you to that last page within a single step.
In programming, plenty of operations are constant: Some examples are:
- Math Operations
- Going through an array via the index
- Going through a hash via the key
- Pushing/ Popping on a stack
- Inserting and removing from a queue
- returning a value from a function
Linear Time or O(n)
Linear time means that the run-time increases at the same as the input.
If we were to take exactly one minute to read a single page, it would take 30 minutes to read 30 pages. So it would take 1000 minutes to read 1000 pages, but I can’t read 50 pages if the books boring. In programming, one of the most common linear time operation would be traversing an array. In Javascript, methods like forEach, map and reduce would run through the dataset from start to finish.
Quadratic Time or O(n²)
Quadratic time means that the calculation in quadratic time, which is squaring the size of the input data.
Many operations of the more basic sorting algorithms have the worst case run time of O(n²)
- Bubble sort
- Insertion Sort
- Selection Sort
If nesting two loops, if the array has n items, the outer loop runs n times and the inner loop runs n times for each iteration of the outer loop, giving us n² of the return.
Logarithmic Time or O(log n)
Logarithmic time means the running time expands in proportion of the logarithm of the input size. Meaning that the run time barely increases as you exponentially increase the input.
If we were to look up the word “Size” in a dictionary, we would open the dictionary and be in the middle of it, because “Size” starts with “s”. We keep repeating this process until we reach the end.
Just like in programming, searching through a dictionary is the same as a binary search operation. I have provided a cheat sheet below to explain the space and time complexity
Big-O Cheat Sheet
To summarize, Big-O Notation is a language we use to describe how much space and time it takes to run an algorithm.
