algorithm course of frontend masters. This first page contains the introduction for the course, and the subsequent sections are listed below.
Big O is a generalized way to be able to understand how an algorithm will react as the input grows. It helps take decisions on which data structures and algorithms to use and how the programs will perform.
Basically: as your input grows, how fast does computation or memory grows?
Important concepts:
Example:
function sum_char_codes(n: string): number {
let sum = 0;
for (let i = 0; i < n.length; ++i) {
sum += n.charCodeAt(i);
}
return sum;
}
To tell how the program grows, the easiest way is to look for loops. This code counts the sum of characters in a string. For each new character added, a new loop has to be done. It means that it grows linearly. If there's 50% more characters, it will take 50% more time. It's called O(N)
.
So what happens when we add a new loop?
Example:
function sum_char_codes(n: string): number {
let sum = 0;
for (let i = 0; i < n.length; ++i) {
sum += n.charCodeAt(i);
}
for (let i = 0; i < n.length; ++i) {
sum += n.charCodeAt(i);
}
return sum;
}
In this example the loop happens twice, so the reflex would be to think it takes twice the time or O(2N)
. But it's not correct: the goal is to describe the growth of the algorithm, not how much time exactly it takes or how much CPU it will use. The number of times it is executed does not change it's growth.
So in this case, the correct notation would be O(2^N)
. This is why constants are dropped in Big O notation.
Example of why constants are not a good indicator, with N as the input:
N = 1, O(10N) = 10, O(N^2) = 1
N = 5, O(10N) = 50, O(N^2) = 25
N = 100, O(10N) = 1,000, O(N^2) = 10,000 // 10x bigger
N = 1000, O(10N) = 10,000, O(N^2) = 1,000,000 // 100x bigger
N = 10000, O(10N) = 100,000, O(N^2) = 100,000,000 // 1000x bigger
Example:
function sum_char_codes(n: string): number {
let sum = 0;
for (let i = 0; i < n.length; ++i) {
const charCode = n.charCodeAt(i);
// Capital E
if (charCode === 69) {
return sum;
}
sum += charCode;
}
return sum;
}
In this example, the sum
is returned when E
is encountered, so logically the growth could be O(n - x)
where x is the number of characters skipped after E
.
But since we don't know where E
is located (it could be at the end, the start, the middle), we consider the worst case scenario, and it means that this growth is O(n)
, as if E
was the last character of the string.
Some algorithms are notoriously heavy in operations and are therefore not recommended, and their Big O notation helps to identify them, as per the graph below (source).
We already saw the O(2^N)
before, here's the O(N^2)
:
function sum_char_codes(n: string): number {
let sum = 0;
for (let i = 0; i < n.length; ++i) {
for (let j = 0; j < n.length; ++j) {
sum += charCode;
}
}
return sum;
}
Same with O(N^3)
:
function sum_char_codes(n: string): number {
let sum = 0;
for (let i = 0; i < n.length; ++i) {
for (let j = 0; j < n.length; ++j) {
for (let k = 0; k < n.length; ++k) {
sum += charCode;
}
}
}
return sum;
}