Time Complexity (Intro)
Understand Big O notation and time complexity — how to describe and compare the efficiency of algorithms.
What you'll learn
- What time complexity is and why it matters
- Big O notation in plain language
- Common complexity classes: O(1), O(n), O(n²), O(log n)
- How to estimate the complexity of your code
- Why algorithm choice matters more than hardware speed
Concept
Time Complexity (Intro)
Time complexity is a way to describe how an algorithm's running time grows as the input size grows. It answers the question: "if I double the input, how much longer does it take?" This matters because an algorithm that is fast for 100 items might be unusably slow for a million — and you want to know that *before* you choose it.
Big O Notation
Big O notation is the language used to express time complexity. It describes the *worst-case* growth rate, ignoring constant factors and lower-order terms. The notation is O(f(n)) where n is the input size and f(n) describes how the work grows.
O(1)— constant time. The work does not depend on input size. Accessing an array element by index is O(1).O(log n)— logarithmic time. Each step halves the problem. Binary search is O(log n).O(n)— linear time. The work is proportional to input size. Scanning a list once is O(n).O(n log n)— linearithmic time. Efficient sorting algorithms (merge sort, quick sort) are O(n log n).O(n²)— quadratic time. The work is proportional to the square of the input. Nested loops over the same data are O(n²).O(2ⁿ)— exponential time. The work doubles with each added item. Naive recursive Fibonacci is O(2ⁿ).
Why It Matters
Consider two algorithms for searching a sorted list of 1,000,000 items:
- Linear search — O(n): check each item. Worst case: 1,000,000 steps.
- Binary search — O(log n): halve the range each time. Worst case: ~20 steps.
That is a 50,000× difference. No amount of hardware speed makes up for a 50,000× algorithmic disadvantage. A faster computer makes both faster, but the *ratio* stays the same. Algorithm choice dominates hardware speed for large inputs.
Estimating Complexity
You can often estimate complexity by looking at the code structure:
// O(1) — constant: one operation regardless of input
function getFirst(arr) { return arr[0]; }
// O(n) — linear: one loop over the input
function sum(arr) {
let total = 0;
for (const x of arr) total += x;
return total;
}
// O(n²) — quadratic: nested loop over the same input
function allPairs(arr) {
for (const a of arr)
for (const b of arr)
console.log(a, b);
}
// O(log n) — logarithmic: halving each step
function binarySearch(arr, target) {
let lo = 0, hi = arr.length - 1;
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
The Practical Takeaway
You do not need to calculate exact Big O for every function. But you should develop an intuition: "this has a nested loop, so it is roughly O(n²) — if n could be 10,000, that is 100 million operations, which might be too slow." That intuition, more than formal proofs, is what makes you a better programmer. When you see a nested loop, ask: "is the inner loop over the same data? If so, this is O(n²) — can I avoid it?"
Constants vs. Growth Rate
Big O ignores constant factors: O(2n) is written as O(n). This is because as n grows, the constant becomes irrelevant. For n = 1,000,000, the difference between n and 2n is a factor of 2 — but the difference between n and n² is a factor of 1,000,000. Big O captures the *growth*, which is what dominates at scale.
Example
// Compare three algorithms with different time complexity.
// Task: Check if an array contains a duplicate value.
// --- O(n²): compare every pair ---
function hasDuplicateSlow(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;
}
// --- O(n log n): sort first, then check neighbors ---
function hasDuplicateMedium(arr) {
const sorted = [...arr].sort((a, b) => a - b);
for (let i = 1; i < sorted.length; i++) {
if (sorted[i] === sorted[i - 1]) return true;
}
return false;
}
// --- O(n): use a Set for O(1) lookups ---
function hasDuplicateFast(arr) {
const seen = new Set();
for (const item of arr) {
if (seen.has(item)) return true;
seen.add(item);
}
return false;
}
// For n = 10, all three are instant.
// For n = 100,000, the O(n²) version takes seconds,
// while the O(n) version takes milliseconds.
const data = Array.from({ length: 10000 }, (_, i) => i);
console.log(hasDuplicateFast(data)); // false (fast)
console.log(hasDuplicateMedium(data)); // false (medium)
// console.log(hasDuplicateSlow(data)); // false (slow — try at your own risk)
Three algorithms solve the same problem with different complexities. The Set-based approach is O(n) because Set.has() is O(1). The nested-loop approach is O(n²). For large arrays, the difference is dramatic — the O(n) version is thousands of times faster.
Try it
- Text Sorter
Sorting is O(n log n) with good algorithms. Try sorting large text and notice it stays fast — that is efficient complexity at work.
- Line Deduplicator
Deduplication can be O(n) with a Set or O(n²) with nested loops. This tool uses the efficient approach.
Common mistakes
The mistake
Using nested loops over the same array without realizing it is O(n²).
The fix
When you see a loop inside a loop over the same data, stop and ask: can I use a Map or Set to avoid the inner loop? Often an O(n²) algorithm can be rewritten as O(n) with a hash-based lookup.
The mistake
Optimizing code prematurely before measuring where the bottleneck actually is.
The fix
Profile first, optimize second. A fast algorithm in a rarely-called function saves nothing. Focus your optimization effort on the code that runs most often or processes the most data.
The mistake
Thinking Big O describes actual running time.
The fix
Big O describes growth rate, not milliseconds. An O(n) algorithm with a slow constant factor can be slower than an O(n²) algorithm for small inputs. Big O matters most for large inputs and for comparing algorithms with different growth rates.
Related Resources
Related Cheatsheets
- JavaScript Cheatsheet
Reference for Set, Map, and array methods that affect algorithmic complexity.
Look up unfamiliar terms
A beginner-friendly glossary explains jargon in plain English — variables, functions, DOM, Promise, and more.
Build real projects
Apply what you learned by building guided projects with starter code and solutions.
Decode error messages
Plain-English explanations of common errors — what they mean, why they happen, and how to fix them.