Engineering Fluency OS

Why This Matters

Imagine you write a search function that works perfectly on 100 items. You ship it, users love it, and the dataset grows to 1,000,000 items. Suddenly the function takes 30 seconds. What went wrong? You never thought about time complexity -- how the runtime of your code grows as the input gets larger.

Big O notation gives you a language to describe and compare algorithm efficiency. It is the single most important concept in computer science interviews, system design, and production engineering. Two functions that produce identical results can differ by orders of magnitude in speed. Big O tells you which one will scale.

Define Terms

Visual Model

O(1)

O(log n)

O(n)

O(n log n)

O(n²)

The full process at a glance. Click Start tour to walk through each step.

As input size grows, the gap between complexity classes widens dramatically.

Code Example

Code

// O(1) - Constant Time
// Accessing by index never depends on array size
function getFirst(arr) {
  return arr[0];
}
console.log(getFirst([10, 20, 30])); // 10

// O(n) - Linear Time
// Must check every element once
function findMax(arr) {
  let max = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) max = arr[i];
  }
  return max;
}
console.log(findMax([3, 7, 2, 9, 1])); // 9

// O(n^2) - Quadratic Time
// Nested loop: every element compared to every other
function hasDuplicate(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;
}
console.log(hasDuplicate([1, 2, 3, 2])); // true

// O(n) - Linear Time (optimized duplicate check)
// Using a Set trades space for time
function hasDuplicateFast(arr) {
  const seen = new Set();
  for (const val of arr) {
    if (seen.has(val)) return true;
    seen.add(val);
  }
  return false;
}
console.log(hasDuplicateFast([1, 2, 3, 2])); // true

Interactive Experiment

Try these exercises:

Write a function that sums all elements in an array. What is its Big O?
Write a function with two nested loops that prints every pair (i, j) from an array. What is its Big O?
Time a linear search vs a Set lookup with arrays of size 100, 1000, and 10000. Do the times match the predictions?
Can you think of a problem where O(1) is impossible and O(n) is the best you can do?

Quick Quiz

Coding Challenge

Optimize from O(n^2) to O(n)

The function `findPairWithSum` below uses a nested loop (O(n^2)) to find two numbers in an array that add up to a target. Rewrite it to run in O(n) time using a Set (JS) or set (Python) to track numbers you have already seen.

Loading editor...

Real-World Usage

Time complexity analysis is critical in production systems:

Database queries: An unindexed query scans every row (O(n)). An indexed lookup is O(log n). At a million rows, that is the difference between seconds and microseconds.
Search engines: Google processes billions of pages because their algorithms are O(log n) or O(1) for lookups, not O(n).
Frontend rendering: Rendering 10,000 list items with an O(n^2) diffing algorithm freezes the browser. React's reconciliation is O(n).
API rate limits: If your endpoint has O(n^2) processing and a user sends n=100,000, you have a denial-of-service vulnerability.
Interview questions: Nearly every coding interview tests your ability to identify and optimize time complexity.

Time Complexity