Suggest an edit

Improve this article

Refine the answer for “How can algorithm complexity be determined?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

**Algorithm complexity** measures how an algorithm's runtime or memory use scales with input size, expressed in Big O notation as a worst-case upper bound.

## Theory

### TL;DR

- Big O counts how operations grow as `n` grows, not how fast your machine runs code.
- Find the dominant operation: the deepest loop or heaviest recursion. Everything else is noise.
- If input doubles and time quadruples, that's O(n²). If time doubles, that's O(n).
- Drop constants: `3n + 5` becomes O(n). The loop dominates when `n` is large.
- Two separate loops over the same array = O(n), not O(2n).

### Quick example

```javascript
// O(1) - constant: doesn't care about array size
function getFirst(arr) {
  return arr[0]; // always 1 operation, whether arr has 3 or 3 million items
}

// O(n) - linear: one loop, one pass
function sum(arr) {
  let total = 0;
  for (let i = 0; i < arr.length; i++) { // n steps
    total += arr[i];
  }
  return total;
}

// O(n²) - quadratic: loop inside a loop
function hasDuplicate(arr) {
  for (let i = 0; i < arr.length; i++) {       // n
    for (let j = i + 1; j < arr.length; j++) { // up to n
      if (arr[i] === arr[j]) return true;
    }
  }
  return false;
}
```

The rule: count the nesting level of your loops. One loop = O(n). Loop inside a loop = O(n²). Each level multiplies.

### Key difference: operations vs lines of code

A common confusion is treating each line of code as "one operation." That only works for fixed-index access like `arr[0]`. The moment your code depends on `n`, the count changes. `arr[i]` inside a loop runs `n` times, not once. Track what scales with input size.

### How to analyze code step by step

Read your code from the inside out:

1. Find the innermost operation (an assignment, comparison, or array access).
2. Count how many times it runs relative to `n`.
3. One surrounding loop = O(n). Two nested loops = O(n²).
4. For recursion, count the depth of the call tree. A function calling itself twice per call gives O(2^n) without memoization.
5. Keep the dominant term only. O(n² + n) simplifies to O(n²).

### When to use each class

- Fixed-size input (under 100 items): O(n²) is fine. You won't notice.
- User data (1K to 1M items): aim for O(n log n) or better. O(n²) will lag.
- Real-time (games, UI interactions): stick to O(1) or O(log n).
- Sorting: the built-in `array.sort()` is O(n log n).

### Complexity classes at a glance

| Complexity | n=10 | n=100 | Example |
|---|---|---|---|
| O(1) | 1 | 1 | `obj.key`, `arr[0]` |
| O(log n) | 3-4 | 7 | Binary search |
| O(n) | 10 | 100 | `array.filter()` |
| O(n log n) | ~33 | ~664 | `array.sort()` |
| O(n²) | 100 | 10,000 | Nested loops, bubble sort |
| O(2^n) | 1,024 | ~10^30 | Naive recursive Fibonacci |

O(n²) at `n=100` means 10,000 operations. At `n=1000`, it's a million. That's the gap that crashes production.

### Common mistakes

**Mistake 1: Thinking chained `.filter().map()` is O(n²)**

```javascript
// O(2n) = O(n) - two separate passes, still linear
const result = arr.filter(x => x > 0).map(x => x * 2);
```

Two loops over the same array add, they don't multiply. O(n + n) = O(2n) = O(n).

**Mistake 2: Hidden nested built-ins**

```javascript
// O(n²) hiding behind clean syntax
arr.map(a => others.includes(a)); // .includes() is O(n) inside an O(n) map
```

Fix: build a `Set` first. `const set = new Set(others); arr.map(a => set.has(a));` drops it to O(n). Most production `.includes()` bugs I've seen come from exactly this pattern.

**Mistake 3: Naive recursion**

```javascript
// O(2^n) - freezes a browser tab at n=50
function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2); // two calls per level = exponential tree
}

// O(n) with memoization
const memo = new Map();
function fibMemo(n) {
  if (memo.has(n)) return memo.get(n);
  if (n <= 1) return n;
  const res = fibMemo(n - 1) + fibMemo(n - 2);
  memo.set(n, res);
  return res;
}
console.log(fibMemo(100)); // instant
```

`fib(40)` technically completes but takes noticeable time. `fib(50)` will freeze the tab. The call tree branches twice at every node.

**Mistake 4: Treating space complexity as an afterthought**

```javascript
function dup(arr) {
  return arr.concat(arr); // O(n) extra space, easy to miss
}
```

If `arr` has 1M items, you just allocated 2M in memory. Space complexity counts auxiliary allocations, not just time.

### Real-world usage

- React: `useMemo` prevents re-running O(n) sorts on every render - `const sorted = useMemo(() => users.sort((a, b) => a.age - b.age), [users])`.
- Express: scanning a DB array for a matching user is O(n). Add a database index and it becomes O(log n).
- Node.js: `readFileSync` is O(n) where `n` is file size. Use streams for large files.
- `Set` vs array: `arr.includes(item)` is O(n). `set.has(item)` is O(1).

### Follow-up questions

**Q:** What's the difference between O(n) and Θ(n)?
**A:** O(n) is an upper bound: the algorithm runs in at most kn operations. Θ(n) is a tight bound: both upper and lower bounds are proportional to n. Interviewers usually mean Θ when they say O, but seniors know the difference.

**Q:** What is the time complexity of this loop?
```javascript
for (let i = 0; i < n; i++)
  for (let j = i; j < n; j++) sum += arr[i][j];
```
**A:** O(n²/2) = O(n²). The inner loop shrinks each iteration, but it's still a triangular traversal. Constants drop.

**Q:** What is the space complexity of quicksort?
**A:** O(log n) average case from recursion stack depth, O(n) worst case. Merge sort is always O(n) because it allocates a temporary array.

**Q:** `array.includes(item)` - what's the Big O?
**A:** O(n). It scans from index 0 every time. Use `Map` or `Set` for O(1) lookup.

## Examples

### Finding the maximum value

```javascript
function findMax(numbers) {
  let max = numbers[0]; // O(1) - one assignment

for (let i = 1; i < numbers.length; i++) { // O(n) - one full pass
    if (numbers[i] > max) max = numbers[i];
  }

return max; // total complexity: O(n)
}

console.log(findMax([3, 7, 1, 9, 4])); // 9
```

The loop runs `n - 1` times. Drop the constant: O(n). The function's complexity is determined by its most expensive operation. Here that's the single pass through the array.

### Filtering a list with set-based lookups

```javascript
const users = [{ id: 1, name: "Alice" }, { id: 2, name: "Bob" }, { id: 3, name: "Carol" }];
const blocked = [1, 5, 7];

// O(n * m) - for each user, scans the entire blocked list
const slow = users.filter(u => blocked.includes(u.id));

// O(n + m) - Set builds once, each lookup is O(1)
const blockedSet = new Set(blocked);
const fast = users.filter(u => !blockedSet.has(u.id));

console.log(fast); // [{ id: 2, name: "Bob" }, { id: 3, name: "Carol" }]
```

The difference is invisible with 3 users and 3 blocked IDs. With 10,000 users and 1,000 blocked IDs, the first version does 10 million comparisons. The second does 11,000.

Markdown · drag & drop images · ⌘B / ⌘I shortcuts1208 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.