Jaconir

What is Big O Notation? A Simple Guide

The ultimate cheat sheet for understanding how we measure an algorithm's efficiency and scalability.

The "Why" Before the "What"

Imagine you have two different ways to find a name in a phone book. Method A is to read every single name from A to Z until you find the one you're looking for. Method B is to open the book to the middle, see if the name is before or after, and then repeat that process on the smaller section. Which one is faster?

Intuitively, you know Method B is much faster, especially for a very large phone book. Big O Notation is simply a formal way to describe this difference. It's not about measuring the exact time in seconds, but about understanding how an algorithm's runtime or space requirements grow as the input size (`n`) grows.

Common Complexities Explained Visually

Here are the most common Big O notations you'll encounter. Use the "Next Step" buttons to see how each algorithm progresses and how it maps to the code.

Visualizing Complexity Growth
Move the slider to see how the number of "operations" (cost) grows for different complexities as the input size ('n') increases.
O(1)
O(log n)
O(n)
O(n²)
O(1) - Constant Time
O(1)
The algorithm takes the same amount of time to run, regardless of the size of the input. It's the fastest and most scalable.
10
20
30
40
50
60
70

Accessing `array[4]` is an instant, direct operation.

1function getElement(arr, index) {
2 return arr[index];
3}

Example: Accessing an item in an array by its index (e.g., `array[5]`).

O(log n) - Logarithmic Time
O(log
The time it takes to run increases with the size of the input, but it does so very slowly. Common in "divide and conquer" algorithms.
10
20
30
40
50
60
70
80
90
100
110
120

Start. Searching for 80 in range [0, 11].

1function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left <= right) {
6 let mid = Math.floor((left + right) / 2);
7 if (arr[mid] === target) {
8 return mid; // Found
9 } else if (arr[mid] < target) {
10 left = mid + 1;
11 } else {
12 right = mid - 1;
13 }
14 }
15 return -1; // Not found
16}

Example: Finding an item in a sorted array using Binary Search.

O(n) - Linear Time
O(n)
The runtime is directly proportional to the size of the input. If the input size doubles, the runtime roughly doubles.
10
50
30
70
20
60
40

Start linear search.

1function findValue(arr, target) {
2 for (let i = 0; i < arr.length; i++) {
3 if (arr[i] === target) {
4 return i; // Found
5 }
6 }
7 return -1; // Not found
8}

Example: Looping through all items in an array to find a specific value.

O(n²) - Quadratic Time
O(n²)
The runtime is proportional to the square of the input size. This is common with nested loops and can get slow very quickly.
10
20
30
40

Start nested loops.

1function findPairs(arr) {
2 let pairs = [];
3 for (let i = 0; i < arr.length; i++) {
4 for (let j = i + 1; j < arr.length; j++) {
5 pairs.push([arr[i], arr[j]]);
6 }
7 }
8 return pairs;
9}

Example: Comparing every element in a list to every other element (e.g., finding all pairs).

Test Your Knowledge
What is the Big O time complexity of the following code snippet?
function getFirstItem(items) {
  return items[0];
}
Coding Challenge
Given an integer array `nums`, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. A simple O(n²) solution involves checking every possible subarray, but the optimal solution (Kadane's Algorithm) is O(n).
Deepen Your Understanding

While this guide covers the basics, the best way to master DSA is through practice and in-depth study. "Cracking the Coding Interview" is considered the bible for this, with hundreds of problems and detailed explanations.

View on Amazon

Next

Arrays & Strings