Skip to content

Time Complexity (Intro)

Understand Big O notation and time complexity — how to describe and compare the efficiency of algorithms.

What you'll learn

  • What time complexity is and why it matters
  • Big O notation in plain language
  • Common complexity classes: O(1), O(n), O(n²), O(log n)
  • How to estimate the complexity of your code
  • Why algorithm choice matters more than hardware speed

Concept

Time Complexity (Intro)

Time complexity is a way to describe how an algorithm's running time grows as the input size grows. It answers the question: "if I double the input, how much longer does it take?" This matters because an algorithm that is fast for 100 items might be unusably slow for a million — and you want to know that *before* you choose it.

Big O Notation

Big O notation is the language used to express time complexity. It describes the *worst-case* growth rate, ignoring constant factors and lower-order terms. The notation is O(f(n)) where n is the input size and f(n) describes how the work grows.

  • O(1) — constant time. The work does not depend on input size. Accessing an array element by index is O(1).
  • O(log n) — logarithmic time. Each step halves the problem. Binary search is O(log n).
  • O(n) — linear time. The work is proportional to input size. Scanning a list once is O(n).
  • O(n log n) — linearithmic time. Efficient sorting algorithms (merge sort, quick sort) are O(n log n).
  • O(n²) — quadratic time. The work is proportional to the square of the input. Nested loops over the same data are O(n²).
  • O(2ⁿ) — exponential time. The work doubles with each added item. Naive recursive Fibonacci is O(2ⁿ).

Why It Matters

Consider two algorithms for searching a sorted list of 1,000,000 items:

  • Linear search — O(n): check each item. Worst case: 1,000,000 steps.
  • Binary search — O(log n): halve the range each time. Worst case: ~20 steps.

That is a 50,000× difference. No amount of hardware speed makes up for a 50,000× algorithmic disadvantage. A faster computer makes both faster, but the *ratio* stays the same. Algorithm choice dominates hardware speed for large inputs.

Estimating Complexity

You can often estimate complexity by looking at the code structure:

// O(1) — constant: one operation regardless of input
function getFirst(arr) { return arr[0]; }

// O(n) — linear: one loop over the input
function sum(arr) {
  let total = 0;
  for (const x of arr) total += x;
  return total;
}

// O(n²) — quadratic: nested loop over the same input
function allPairs(arr) {
  for (const a of arr)
    for (const b of arr)
      console.log(a, b);
}

// O(log n) — logarithmic: halving each step
function binarySearch(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

The Practical Takeaway

You do not need to calculate exact Big O for every function. But you should develop an intuition: "this has a nested loop, so it is roughly O(n²) — if n could be 10,000, that is 100 million operations, which might be too slow." That intuition, more than formal proofs, is what makes you a better programmer. When you see a nested loop, ask: "is the inner loop over the same data? If so, this is O(n²) — can I avoid it?"

Constants vs. Growth Rate

Big O ignores constant factors: O(2n) is written as O(n). This is because as n grows, the constant becomes irrelevant. For n = 1,000,000, the difference between n and 2n is a factor of 2 — but the difference between n and n² is a factor of 1,000,000. Big O captures the *growth*, which is what dominates at scale.

Example

              // Compare three algorithms with different time complexity.
// Task: Check if an array contains a duplicate value.

// --- O(n²): compare every pair ---
function hasDuplicateSlow(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) return true;
    }
  }
  return false;
}

// --- O(n log n): sort first, then check neighbors ---
function hasDuplicateMedium(arr) {
  const sorted = [...arr].sort((a, b) => a - b);
  for (let i = 1; i < sorted.length; i++) {
    if (sorted[i] === sorted[i - 1]) return true;
  }
  return false;
}

// --- O(n): use a Set for O(1) lookups ---
function hasDuplicateFast(arr) {
  const seen = new Set();
  for (const item of arr) {
    if (seen.has(item)) return true;
    seen.add(item);
  }
  return false;
}

// For n = 10, all three are instant.
// For n = 100,000, the O(n²) version takes seconds,
// while the O(n) version takes milliseconds.
const data = Array.from({ length: 10000 }, (_, i) => i);
console.log(hasDuplicateFast(data));     // false (fast)
console.log(hasDuplicateMedium(data));   // false (medium)
// console.log(hasDuplicateSlow(data));   // false (slow — try at your own risk)
            

Three algorithms solve the same problem with different complexities. The Set-based approach is O(n) because Set.has() is O(1). The nested-loop approach is O(n²). For large arrays, the difference is dramatic — the O(n) version is thousands of times faster.

Try it

  • Text Sorter

    Sorting is O(n log n) with good algorithms. Try sorting large text and notice it stays fast — that is efficient complexity at work.

  • Line Deduplicator

    Deduplication can be O(n) with a Set or O(n²) with nested loops. This tool uses the efficient approach.

Common mistakes

The mistake

Using nested loops over the same array without realizing it is O(n²).

The fix

When you see a loop inside a loop over the same data, stop and ask: can I use a Map or Set to avoid the inner loop? Often an O(n²) algorithm can be rewritten as O(n) with a hash-based lookup.

The mistake

Optimizing code prematurely before measuring where the bottleneck actually is.

The fix

Profile first, optimize second. A fast algorithm in a rarely-called function saves nothing. Focus your optimization effort on the code that runs most often or processes the most data.

The mistake

Thinking Big O describes actual running time.

The fix

Big O describes growth rate, not milliseconds. An O(n) algorithm with a slow constant factor can be slower than an O(n²) algorithm for small inputs. Big O matters most for large inputs and for comparing algorithms with different growth rates.

Related Cheatsheets

Look up unfamiliar terms

A beginner-friendly glossary explains jargon in plain English — variables, functions, DOM, Promise, and more.

View glossary

Build real projects

Apply what you learned by building guided projects with starter code and solutions.

View projects

Decode error messages

Plain-English explanations of common errors — what they mean, why they happen, and how to fix them.

View errors