Big-O in Programming: Learn It by Counting How Much Work Your Code Does

SEO description: A beginner-friendly teaching guide to Big-O notation, algorithm complexity, O(1), O(log n), O(n), O(n log n), O(n²), loop analysis, code optimization, exercises, and answers.

Keywords: Big-O, algorithm complexity, time complexity, space complexity, programming basics, code optimization, algorithms.

Learning goal: By the end of this lesson, you should be able to read a simple piece of code and explain how its workload grows as the input gets larger.

Image source: original PNG chart created for this article, based on asymptotic notation and growth-rate concepts explained by MIT, Khan Academy, and Princeton. No SVG is used.

1. What is Big-O in plain language?

Big-O describes how an algorithm’s workload grows as the input size grows. It does not mainly ask, “How many exact milliseconds will this take?” It asks, “If the input grows from 100 items to 10,000 items, how does the amount of work grow?”

Khan Academy describes Big-O as an asymptotic upper bound on running time for sufficiently large input sizes. In practical programming terms, Big-O tells you how quickly an algorithm gets worse as the data grows. Source: Khan Academy - Big-O notation.

MIT also uses Big-O to describe an algorithm’s “order of growth.” Source: MIT - Big O notation PDF.

2. Imagine you are checking a class list

Suppose you have a list of students and need to find a student named “Anna.”

If the list is not sorted, you may need to check students one by one:

function findStudent(students, name) {
  for (const student of students) {
    if (student.name === name) return student;
  }
  return null;
}

If there are 10 students, the worst case may require 10 checks. If there are 1,000 students, it may require 1,000 checks. If there are 1,000,000 students, it may require 1,000,000 checks.

This is O(n) because the amount of work grows roughly in proportion to the number of items.

Rule of thumb: one loop through all input items is usually O(n).

3. Common Big-O classes

O(1): direct access, independent of input size

function getFirst(items) {
  return items[0];
}

Whether the array has 10 items or 10 million items, the algorithmic idea is still one direct access.

Memory cue: no loop over n, no search, no full traversal.

O(n): one full pass

function sum(numbers) {
  let total = 0;
  for (const number of numbers) {
    total += number;
  }
  return total;
}

The code does one addition per item. 100 items means about 100 iterations. 1 million items means about 1 million iterations.

O(n²): each item is compared with many other items

function hasDuplicate(numbers) {
  for (let i = 0; i < numbers.length; i++) {
    for (let j = i + 1; j < numbers.length; j++) {
      if (numbers[i] === numbers[j]) return true;
    }
  }
  return false;
}

This is the classic nested-loop example. If n grows 10 times, the number of comparisons may grow about 100 times.

Memory cue: two loops over the same input often suggest O(n²).

O(log n): each step removes a large part of the remaining data

A common example is binary search on a sorted array.

function binarySearch(sortedNumbers, target) {
  let left = 0;
  let right = sortedNumbers.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (sortedNumbers[mid] === target) return mid;
    if (sortedNumbers[mid] < target) left = mid + 1;
    else right = mid - 1;
  }

  return -1;
}

Each check removes about half of the remaining data. With 1,000,000 items, repeated halving takes only around 20 steps.

Khan Academy’s algorithms material covers binary search and running time as a useful example of this growth pattern. Source: Khan Academy - Algorithms.

O(n log n): common in efficient sorting algorithms

Many efficient sorting algorithms have O(n log n) growth. A simple way to think about it: the algorithm processes n items, while also splitting or merging work across multiple layers.

You do not need to memorize every sorting algorithm at first. Just remember that efficient comparison-based sorting commonly brings O(n log n) into the discussion.

4. How to read Big-O from code: a 4-step method

Step 1: Identify what n means. It may be the number of users, rows, array items, tree nodes, or characters in a string.

Step 2: Look for loops or repeated operations tied to n. One full pass is usually O(n).

Step 3: Check whether loops are nested. If each item triggers another pass through the same input, suspect O(n²).

Step 4: Drop constants and smaller terms. O(2n) becomes O(n). O(n + 100) becomes O(n). O(n² + n) becomes O(n²), because n² dominates as n grows.

5. Step-by-step teaching example: detecting duplicates

Problem: check whether an array contains a duplicate value.

Approach 1: compare every pair.

function hasDuplicateSlow(numbers) {
  for (let i = 0; i < numbers.length; i++) {
    for (let j = i + 1; j < numbers.length; j++) {
      if (numbers[i] === numbers[j]) return true;
    }
  }
  return false;
}

Analysis: the outer loop grows with n. For each outer iteration, the inner loop checks many remaining items. Overall, this is O(n²).

Approach 2: use a Set to remember what you have already seen.

function hasDuplicateFast(numbers) {
  const seen = new Set();

  for (const number of numbers) {
    if (seen.has(number)) return true;
    seen.add(number);
  }

  return false;
}

Analysis: the array is traversed once. In common algorithmic reasoning, this is treated as average O(n), with extra O(n) memory for the Set.

Lesson: optimization often trades memory for time.

6. Time complexity vs. space complexity

Time complexity asks: how many steps does the program need as input grows?

Space complexity asks: how much extra memory does the program need as input grows?

hasDuplicateSlow uses little extra memory but can be slow: O(n²) time, O(1) extra space.

hasDuplicateFast is faster on large inputs but uses more memory: O(n) average time, O(n) extra space.

In practice, O(n) is not automatically better in every situation. If the input is small, the simpler version may be sufficient. If the input is large, Big-O becomes much more important.

Princeton notes that Big-O should not be misused as a precise performance predictor. It describes growth order, while real speed still depends on hardware, language, cache behavior, runtime, and implementation details. Source: Princeton - Analysis of Algorithms.

7. Quick reference table

8. Common misunderstandings

Mistake 1: “Two loops always mean O(n²).” Not always. Two separate loops may still be O(n).

function twoSeparateLoops(items) {
  for (const item of items) console.log(item);
  for (const item of items) console.log(item);
}

This is O(n), not O(n²).

Mistake 2: “Big-O gives the exact runtime.” It does not. Big-O describes growth, not exact milliseconds.

Mistake 3: “O(n) is always faster than O(n log n).” For small inputs or algorithms with large hidden constants, real results may differ. But for very large n, growth order tends to matter more.

Mistake 4: “Optimizing Big-O is all that matters.” It is not. Code also needs to be correct, readable, maintainable, and appropriate for real data.

9. Practice questions

Question 1

What is the Big-O of this code?

function printAll(items) {
  for (const item of items) {
    console.log(item);
  }
}

Question 2

What is the Big-O of this code?

function printPairs(items) {
  for (const a of items) {
    for (const b of items) {
      console.log(a, b);
    }
  }
}

Question 3

What is the Big-O of this code?

function printFirstThenAll(items) {
  console.log(items[0]);

  for (const item of items) {
    console.log(item);
  }
}

Question 4

You have 1 million usernames and need to check whether a username exists. Would you prefer scanning an array or using a fast lookup structure such as a Set/Map? Why?

10. Answers

Question 1: O(n). There is one loop over the input.

Question 2: O(n²). For each a, the code loops over every b.

Question 3: O(n). The first access is O(1), the loop is O(n), so O(n + 1) simplifies to O(n).

Question 4: Prefer a Set/Map-like lookup structure if you need repeated existence checks on large data. Scanning an array may require many checks, while lookup-oriented structures are designed to find items faster in practice. The tradeoff is extra memory.

11. Real-code analysis checklist

• What does n represent?
• Is there a loop tied to n?
• Are loops nested?
• Does each step divide the search space?
• Does the code allocate a new array/object/set/map based on input size?
• Is the code trading memory for time?
• Is the real data large enough to justify optimization?

12. Lesson summary

Big-O is a tool for reading how fast an algorithm’s workload grows. Beginners do not need to turn it into heavy mathematics immediately. Start by looking at loops, input size, and how many times the code must work.

If code makes one full pass, think O(n). If it has nested loops over the same data, suspect O(n²). If each step removes half of the remaining data, think O(log n). If you improve code from O(n²) to O(n), you are often using extra memory to save time.

References

• Khan Academy - Big-O notation
• Khan Academy - Algorithms
• MIT - Big O notation PDF
• Princeton - Analysis of Algorithms
• Python Wiki - TimeComplexity