Jaconir
Skip to lesson
FoundationsPatternsGraphs / DPInterview
easy
20 minMostly intern / new-grad

When to use. Whenever you write or review an algorithm — before optimizing, after choosing a structure.

Complexity. Time The bound you are measuring (O(1) through O(n²) and beyond). Space Extra memory besides the input; mention it in the same breath as time.

Who gets asked. Interns are asked to name the complexity of their code. Seniors are expected to state it unprompted and defend tradeoffs.

Prereq. Comfortable writing a for-loop.

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. In interviews, say the bound before you code. Interns are asked to name it; seniors are expected to volunteer time and extra space, and to name the worst case (hash collisions, unbalanced trees).

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
Largest sum of any non-empty contiguous subarray. Nested loops are O(n²). Kadane is O(n) time, O(1) extra: drop a prefix once its running sum is negative.

Saved in this browser. No account.

NextArrays & Strings