Suggest an edit

Improve this article

Refine the answer for “Input size and performance”. 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)

**The larger the input, the longer the code runs, unless the algorithm scales well.** The relation between input size and the amount of work is described by asymptotic complexity (Big O), and it is that relation, not the raw speed of a single operation, that decides whether the code survives growth.

## Theory

### TL;DR
- Input size affects CPU time, memory use, the number of I/O operations, the number of iterations and the recursion depth.
- Big O shows how fast the running time grows as `n` increases, not how many milliseconds one call takes.
- At `n = 10` there is no difference between `O(n)` and `O(n²)`; at `n = 100 000` it decides whether the app works at all.
- Lookup in a `Map` or `Set` is nearly `O(1)`, lookup in an array is `O(n)`, nested loops are `O(n²)`.
- Long synchronous loops block the event loop: the interface freezes and FPS drops.
- The main remedies: better data structures, memoization, chunking the work, list virtualization, streaming.

### Quick example
```javascript
// O(n): time grows in proportion to the number of elements
function sum(arr) {
  return arr.reduce((acc, num) => acc + num, 0);
}

sum([1, 2, 3]);              // roughly 3 operations
sum(new Array(1000000));     // roughly 1 000 000 operations

// O(n^2): time grows as the square of the number of elements
function allPairs(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      // some operation on the pair
    }
  }
}
// n = 1 000    -> about 1 000 000 operations
// n = 10 000   -> already 100 000 000 operations
```

### Asymptotic complexity: how time grows

| Complexity | Name | What it means | Example |
| --- | --- | --- | --- |
| **O(1)** | constant | independent of the data size | index access `arr[0]` |
| **O(log n)** | logarithmic | grows very slowly | binary search |
| **O(n)** | linear | time grows in proportion to the element count | a `for` loop over an array |
| **O(n log n)** | quasilinear | moderate growth | `Array.prototype.sort()` |
| **O(n²)** | quadratic | explosive growth on large inputs | nested loops |
| **O(2ⁿ)** | exponential | grows catastrophically | naive recursive Fibonacci |
| **O(n!)** | factorial | impossible for large `n` | generating all permutations |

The same table from the user's point of view:

| Input size | O(1) | O(log n) | O(n) | O(n²) | O(2ⁿ) |
| --- | --- | --- | --- | --- | --- |
| 10 | instant | instant | instant | instant | instant |
| 100 | instant | instant | instant | noticeable | slow |
| 1 000 | instant | instant | noticeable | slow | impossible |
| 100 000 | instant | instant | slow | impossible | impossible |

The conclusion: on small inputs anything flies, and inefficiency shows up exactly when the volume has grown.

### JavaScript examples
`O(1)`, access does not depend on size:

```javascript
const arr = [1, 2, 3, 4, 5];
console.log(arr[3]); // instant, whether there are 5 or 5 million elements
```

`O(n)`, linear dependence:

```javascript
function sum(arr) {
  return arr.reduce((acc, num) => acc + num, 0);
}
```

The bigger the array, the more time: every element is processed exactly once.

`O(n²)`, quadratic growth:

```javascript
function allPairs(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      // some operation
    }
  }
}
```

If `n = 1000` that is roughly **1 000 000** operations. If `n = 10 000`, already **100 000 000**.

`O(2ⁿ)`, exponential growth:

```javascript
function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

fib(30); // works
fib(45); // already visibly slow
```

The growth is explosive: at around `n = 100` computing it is simply impossible.

### Where it shows up in practice

| Kind of task | Example | How input size affects it |
| --- | --- | --- |
| **Iterating an array** | `map`, `filter`, `reduce` | linearly |
| **Searching an array** | `arr.includes()` | linearly |
| **Lookup in an object or Map** | `obj[key]`, `map.get()` | nearly `O(1)` |
| **Sorting** | `arr.sort()` | `O(n log n)` |
| **Comparing nested structures** | deep object comparison | can be `O(n²)` |
| **Rendering in React** | large lists, tables | time grows with the DOM size |
| **Database queries** | without an index it is `O(n)` | the more rows, the slower |

Practical consequences of growing data:

- **CPU load rises**: operations take longer.
- **Memory use increases**, especially when copying or storing large structures.
- **The event loop is blocked**: the interface freezes and clicks are not handled.
- **FPS drops**: animations become choppy.
- **The garbage collector runs more often**, which produces visible lag.
- **Deeper recursion** raises the risk of `RangeError: Maximum call stack size exceeded`.

### What to do when the data grows

| Problem | Solution |
| --- | --- |
| Loops run for too long | Split the work into chunks (`setTimeout`, `requestIdleCallback`) |
| Complex filters and searches | Use `Set`, `Map`, prebuilt indexes |
| Frequent repeated computation | Memoization |
| Too many DOM elements | List virtualization (`react-window`, infinite scroll) |
| Constantly recreating arrays | Use mutation carefully instead of copying |
| Large JSON payloads | Streaming reads (`ReadableStream`) |
| Heavy computation on the UI thread | Move it into a Web Worker |

A summary map of the impact:

| What grows | What it affects |
| --- | --- |
| Number of iterations | Execution time |
| Recursion depth | Risk of stack overflow |
| Number of objects | Memory usage |
| List or array length | Number of re-renders in React |
| I/O volume | Latency from the network or disk |

### Common mistakes
1. **Optimizing the constant instead of the complexity.** Swapping `for` for `while` in the name of speed is pointless if the algorithm is still `O(n²)`: the right data structure buys a thousandfold win, a micro-optimization buys percents.
2. **Testing only on small inputs.** Anything works on 20 records; problems surface at real volumes, so load checks must use data close to production.
3. **Searching an array inside a loop.** `arr.includes(x)` inside a loop over another array turns the task into `O(n * m)`; a prebuilt `Set` makes it linear.
4. **Forgetting the hidden cost of built-in methods.** `arr.splice()`, `arr.shift()` and `arr.unshift()` shift elements and cost `O(n)`, and a `filter().map().reduce()` chain walks the array three times.
5. **Assuming `O(1)` is always faster than `O(n)`.** For very small `n` a plain linear scan can beat building a hash structure: asymptotics describe behaviour under growth, not absolute time.
6. **Blocking the main thread with a synchronous loop.** While the loop runs the browser neither paints nor reacts to events, so the user sees a freeze even if the total time is acceptable.
7. **Ignoring memory.** An algorithm can be `O(n)` in time yet allocate `O(n)` on each step, and growth then hits the garbage collector rather than the CPU.

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

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.