Back to Catalog
Big O
Acceptable
O(n) - Linear Time
Touch every element exactly once ā unavoidable when you need to see all the data.
Intent & Description
Real-world Use Case
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.
Source
š TL;DR
O(n) = visit every element once. Unavoidable for full-scan problems. Keep it to one pass. If your data is sorted, ask yourself if O(log n) is achievable instead.
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
Disadvantages
- 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)
Implementation Example
// 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;
}