# O(n) - Linear Time

> Touch every element exactly once — unavoidable when you need to see all the data.

- **Category**: Big O
- **Subcategory**: Acceptable
- **Canonical URL**: https://designpattern.fyi/patterns/linear-time/

---

## Description
Clean, reusable architecture pattern.


## Use Cases
Finding the max value in an unsorted array, counting word frequency in a document, validating all items in a shopping cart, reading every row from a database cursor. Any "scan everything once" operation.



## Implementation Example

```javascript
// O(n) — Find max in one pass
function findMax(arr) {
  let max = -Infinity;
  for (const x of arr) max = x > max ? x : max; // One pass, no nested loops
  return max;
}

// O(n) — Combine multiple operations in a single pass (practical optimization)
function stats(arr) {
  let min = Infinity, max = -Infinity, sum = 0;
  for (const x of arr) {       // One loop instead of three separate O(n) passes
    if (x < min) min = x;
    if (x > max) max = x;
    sum += x;
  }
  return { min, max, avg: sum / arr.length };
}

// O(n) — Frequency map (prerequisite for many O(n) solutions)
function charFrequency(str) {
  const freq = {};
  for (const ch of str) freq[ch] = (freq[ch] || 0) + 1; // One pass
  return freq;
}

// O(n) — Two-pointer technique (avoids O(n²) nested loop)
function twoSum(sortedArr, target) {
  let lo = 0, hi = sortedArr.length - 1;
  while (lo < hi) {
    const sum = sortedArr[lo] + sortedArr[hi];
    if (sum === target) return [lo, hi];
    sum < target ? lo++ : hi--;
  }
  return null;
}

```



## Trade-offs


### Advantages

- Simple and straightforward — one loop, easy to reason about

- Often the theoretical minimum for problems requiring full data examination

- Linear memory access patterns are cache-friendly on modern CPUs

- Streaming-friendly — can process data larger than RAM one chunk at a time




### Considerations & Drawbacks

- Slower than O(log n) for searchable/sorted data — if data is sorted, binary search beats this

- Can feel slow for very large n (tens of millions of records in a tight loop)

- Multiple O(n) passes can add up — three separate loops is still O(n) but 3x slower in practice

- Not suitable for operations that can be precomputed or cached to O(1)







---
**Reference**: [Original Source](https://www.bigocheatsheet.com)