Big-O had became one of the subjects about Computer Science that is more discussed on the social media -- specially on X (RIP Twitter).
But, the question is: It is so hard to find a starter -- with no academic background -- that knows what this means.
So, I am writing this article in order to be your first absolute contact with the Big-O notations.
Preface
Big-O is a very special notation that was created to tell you how faster is your algorithm.
It is unfair to calculate the speed of your algorithm using time as a reference, because, it may depends on a lot of points and specific hardware configs such as: available VRAM, processing power, video card, etc.
So, the right way to measure a algorithm speed is through steps. If your algorithm X takes 7 steps in order to be finished and the Y one takes 32, the X will always be quicker to run.
What does Big-O mean?
I know this could sound kinda silly, but, basically, in order to give a symbol to que Operation function, the mathematicians gave it the name "O", and the "(n)" or "(1)" after the symbol are its operation count.
It is called Big-O because of the "O" that comes before the count is much bigger than the other letters, so it looks like a big O around other operations.
Types of Big-O operations
- O(log n) - logarithmic time
- O(n) - linear time
- O(n * log n) - quick order time
- O(n^2) - slow order time
- O(n!) - slower order time
Examples of algorithms with different Big-O notations
O(log n)
Suppose you are looking for a book in a library where the books are arranged alphabetically by title. Write an algorithm that quickly finds the location of the book on the shelf using the binary search strategy.
function binarySearch(books: string[], target: string): number {
let left = 0;
let right = books.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (books[mid] === target) {
return mid; // Encontrou o livro na posição mid
} else if (books[mid] < target) {
left = mid + 1; // O livro alvo está à direita do meio
} else {
right = mid - 1; // O livro alvo está à esquerda do meio
}
}
return -1; // O livro alvo não foi encontrado na biblioteca
}
const libraryBooks = [
"Alice in Wonderland",
"Harry Potter and the Sorcerer's Stone",
"Pride and Prejudice",
"The Great Gatsby",
"To Kill a Mockingbird",
"War and Peace",
];
const targetBook = "The Great Gatsby";
const bookLocation = binarySearch(libraryBooks, targetBook);
if (bookLocation !== -1) {
console.log(`The book "${targetBook}" is located at index ${bookLocation}.`);
} else {
console.log(`The book "${targetBook}" was not found in the library.`);
}
In this algorithm, we use binary search to quickly find the location of the book on the library shelf. At each step, we divide the book list in half and compare the target book title with the title in the middle of the list. This allows us to find the desired book in a relatively small number of iterations, making its running time O(log n), where 'n' is the number of books in the library.
O(n)
Imagine that you are adding up the total expenses on an expense list. Each expense is represented by an integer in the list. Write an algorithm that calculates the total spend.
function calculateTotalExpenses(expenses: number[]): number {
let total = 0;
for (const expense of expenses) {
total += expense;
}
return total;
}
const expensesList = [100, 50, 75, 120, 200];
const totalSpent = calculateTotalExpenses(expensesList);
console.log(`Total expenses: $${totalSpent}`);
In this algorithm, we are summing all the elements in the expense list using a for loop. With each iteration of the loop, we add the expense amount to the total variable. As each expense is considered once, the number of operations is directly proportional to the number of elements in the list, that is, the complexity is O(n), where 'n' is the size of the list.
O(n * log n)
Suppose you are sorting a list of names alphabetically. Write an algorithm that sorts the names alphabetically using an optimized approach.
function mergeSort(arr: string[]): string[] {
if (arr.length <= 1) {
return arr;
}
const mid = Math.floor(arr.length / 2);
const left = arr.slice(0, mid);
const right = arr.slice(mid);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left: string[], right: string[]): string[] {
const result = [];
let leftIndex = 0;
let rightIndex = 0;
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] < right[rightIndex]) {
result.push(left[leftIndex]);
leftIndex++;
} else {
result.push(right[rightIndex]);
rightIndex++;
}
}
return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}
const namesList = ["Emma", "Liam", "Olivia", "Noah", "Ava", "William"];
const sortedNames = mergeSort(namesList);
console.log("Sorted names:", sortedNames);
In this algorithm, we use the Merge Sort sorting algorithm to sort the list of names alphabetically. Merge Sort divides the list into two halves until each sublist contains only one element. It then combines and sorts the sublists into a single sorted list. The complexity of the Merge Sort is O(n * log n), where 'n' is the size of the list, due to the splits and combinations of the sublists that occur in a log n of steps and the subsequent combination at each step will take O(n ) time.
O(n^2)
Suppose you are sorting a list of letters alphabetically using the insertion sort method. Write an algorithm that sorts the cards in the correct order.
function insertionSort(arr: string[]): string[] {
for (let i = 1; i < arr.length; i++) {
const currentCard = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > currentCard) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = currentCard;
}
return arr;
}
const unsortedCards = ["Spades", "Hearts", "Clubs", "Diamonds"];
const sortedCards = insertionSort(unsortedCards);
console.log("Sorted cards:", sortedCards);
In this algorithm, we are using the insertion sort method to arrange a list of cards in alphabetical order. The algorithm loops through the list and, for each element, inserts it into the correct position within the already sorted part of the list on the left. As we are comparing all elements to each other and performing repeated insertions, the complexity of the algorithm is O(n^2), where 'n' is the number of elements in the list.
Although insertion sort is not the most efficient approach to sorting large lists, it is a useful analogy for understanding algorithms with quadratic complexity.
O(n!)
Suppose you are organizing a music event and you need to plan the order of presentations for several bands. Write an algorithm that generates all possible playing orders for the bands.
function generatePermutations(elements: string[]): string[][] {
if (elements.length === 0) {
return [[]];
}
const firstElement = elements[0];
const restElements = elements.slice(1);
const partialPermutations = generatePermutations(restElements);
const allPermutations = [];
for (const partialPermutation of partialPermutations) {
for (let i = 0; i <= partialPermutation.length; i++) {
const newPermutation = [...partialPermutation.slice(0, i), firstElement, ...partialPermutation.slice(i)];
allPermutations.push(newPermutation);
}
}
return allPermutations;
}
const bands = ["Band A", "Band B", "Band C"];
const bandPermutations = generatePermutations(bands);
console.log("Possible band orders:", bandPermutations);
In this algorithm, we are generating all possible permutations of the bands to create different order of presentation. The algorithm uses recursion to compute all permutations, combining each element with the remaining partial permutations. As the number of permutations grows exponentially with the number of elements (n!), the complexity of this algorithm is O(n!).
Although generating permutations is a computationally intensive task, it is not very practical for large sets of elements because of the rapid increase in the number of permutations as the number of elements increases.
Final considerations
Understanding what Big-O means will help you participate on much deep debates about Computer Science and understand that having an algorithm that runs in 10ms is not a synonym of optimization.
Thumbnail by Mohsen Samimi on Unsplash
Top comments (0)