Big-O Notation
Intro
This is an extremely important concept, Big-O is the term we use to identify the efficiency of an algorithm. It is essential that you fully understand it as it will help you understand how slow or fast your algorithms run.
Remember that an algorithm is a set of instructions or rules - ordered and defined in a way that typically allows you to solve a problem, perform computations, process data, etc.
I will try to explain with an analogy. Imagine that my little niece Ariana starts collecting stamps. Quickly she collects a collection of a 100 stamps. At that point she notices that she needs a way of finding a stamp inside her collection, an algorithm! There are 2 that quickly come to mind, Simple Search and Binary Search. Each algorithm has its pros and cons.
Simple Search is easier to write and less prone to bugs, but the algorithm takes 1 second for each lookup of a stamp, so the search takes 100 seconds. On the other hand, Binary Search is faster. Log2 (100) = 7 seconds (don't worry about the math for now).
You can find simple explanations on pages like these. Just remember that when we say that Log2 (8) = 3, this means that we need to multiply 2 (the base) 3 times to reach 8.
Note: it is not important that you know logarithms in depth, but it is useful to have some notion of how they work - Video.
For now we know that 100 seconds is not much of a problem when we're looking for a specific stamp, but what would happen if Ariana's collection grew to 1 million stamps?
The Simple Search algorithm would take 1,000,000 seconds - the equivalent of more than 11 days. Binary Search on the other hand would take 20 seconds to find the stamp. With this we can see that the algorithm scales significantly as the number of operations increases. It is also important to realize that Big-O denotes the worst possible case of our algorithm, since it would also be possible for us to find the stamp at the index number 3 if we were lucky. However this concept is not useful when defining if an algorithm is efficient.
Then we could define that our Simple Search is defined as O(N). O referring to Big-O and N to the number of operations required. In the case of 100 stamps, the Big-O of Simple Search would be denoted as O(100).
The most common types of Big-O
It is important to note that the efficiency of an algorithm is not measured in seconds. It is measured in the increase in the number of operations required.
Let's visualize different types of Big-O
O (N) - Linear Runtime
This means that the number of operations required will be the same as the number of elements that we have to iterate. Imagine this code, that finds the lowest and highest value in an array. This is written as O(N).
int[] intArray = {1,5,10,20,2,6,12};
int min = Integer.MIN_VALUE;
int max = Integer.MAX_VALUE;
for (int x : intArray) {
if (x < min ) min = x;
if (x > max) max = x;
}
Note: It is important to note that in the case of Big-O notation we will try to ignore other constants such as O (2N), O (N * 2) etc. since it is not of importance to us for reasons that I prefer not to explain here. We could go to assembly code to disapprove this issue. Here I explain with an example:
int[] intArray = {1,5,10,20,2,6,12};
int min = Integer.MIN_VALUE;
int max = Integer.MAX_VALUE;
for (int x : intArray) {
if (x < min ) min = x;
}
for (int x : intArray) {
if (x > max) max = x;
}
In this case, although we will iterate twice, it is always on the same array. Many people would think that it would be expressed as O(2N) or as O(N * 2), but in truth it is written as O(N).
Examples:
- Traversing an array
- Traversing a linked list
- Linear Search (Simple Search)
- Comparing two Strings
- Removing an item from a Linked List (Unordered)
- Finding a Palindrome
Multi-part algorithms (sum and multiplication)
A source of constant confusion is when we have multiple data sets on which we will operate. These cases are covered with addition and multiplication.
Sum
Summation is very simple, it is obtained when we have two separate data structures. This example would be written as O(A + B).
int[] arrayA = {1,5,10,20,2,6,12};
int[] arrayB = {100,200,300,400,500,600};
for (int x : arrayA) {
if (x < min ) min = x;
}
for (int x : arrayB) {
if (x > max) max = x;
}
Multiplication
To perform multiplication we have to perform operations on the data structure B within the data structure A. This example would be written as O(A * B).
int[] arrayA = {1,5,10,20,2,6,12};
int[] arrayB = {100,200,300,400,500,600};
for (int x : arrayA) {
for (int y : arrayB) {
System.out.println(x + y);
}
}
O(1) - Constant Runtime
This refers to the fact that the number of operations will always be the same and is the fastest possible operation.
int returnFirst(int[] array) {
return array[0];
}
Examples:
- Accessing an array by its index
- Inserting a node into a Linked List
- Pushing / popping in a stack
- Inserting / removing a queue (tail)
O (Log N) - Logarithmic Runtime
As we talked about at the beginning, the clearest example of this is Binary Search. This refers to when we repeatedly divide the amount of operations needed by 2. Let's look at this example:
int[] array = {0,1,2,3,4,5,6,7,8,9,10}; // Ordered
If Binary Search wanted to find the number 9, it would start by finding the middle number as a pivot - in this case the number 5. Now knowing that the array is ordered, it knows that, in order to reach 8, it has to be > 5. Then it decides to only look at the remaining numbers on the right side of the array.
int[] array = {6,7,8,9,10} // Remaining Array
Again the middle number is obtained as a pivot - in this case the 8. We know that 9 > 8 so we decide to look again at the the elements on the right side of the pivot: {9,10}. In the next operation, we will only have 2 elements and we will know that one of those two is the one we are looking for.
int[] array = {9, 10} // Remaining Array
As you can see after each operation, N is reduced by half: N / 2 -> N / 4 -> N / 8, etc. This may happen until N becomes 1 in the worst case. The key here is to know how to identify when a solution continues to reduce the amount of operations by half is when we refer to O(Log N).
Examples:
- Binary Search
- Finding the highest / lowest number in a Binary Search Tree
O(N ^ 2) - Quadratic runtime
Quadratic refers to the worst possible time being directly proportional to the size of the squared data structure.
for (let x: array) {
for (let y: array) {
System.out.println(x + y);
}
}
Examples:
- Bubble Sort
- Insertion Sort
- Selection Sort
- Crossing a 2D array
O (N log N) - Linearithmic runtime
Linearithmic refers to when we run a logarithmic operation N Log N a number of times, N. Most sorting algorithms are like this. These are quite long to explain here, but in the algorithm part I will explain these kind of problems later.
Examples:
- Merge Sort
- Heap Sort
- Quick Sort
O(2 ^ N) - Exponential runtime
This occurs when, for each increase in the size of the data structure, the runtime doubles. For a small data set, this algorithm will not seem like much, but as the data set increases in size, the runtime increases dramatically. An example is a recursive solution to find Fibonacci.
int fibonacci(int n) {
if (n <= 1) return 1;
return fibonacci(n - 2 ) + fibonacci(n - 1);
}
O(N!) - Factorial runtime
This is the worst case. For example, an algorithm that looks for every possible permutation in a data structure will be N!
Recursive Algorithms
Let's look at the following recursive algorithm:
int f(intn) {
if(n == 1) return1;
returnf(n - 1) + f(n - 1);
}
Many programmers would think that this is solved in a certain logarithmic way, but for this there is a very easy formula, it is branches raised to depth: O(Branches ^ Depth). Now I will explain. Let's imagine that with this simple recursive algorithm we introduce the number 4. Something like this would happen:
Here we can see that when we call the function with the number 4 really generates 4 degrees of depth, since the algorithm has “2 branches” and by this I mean the number of times the function is recursively calling itself. With this we can derive that in this case the time for this algorithm would be O(2 ^ N).