How Algorithms Scale with Input Size: Breaking Down Big-O
Source: Dev.to
Big‑O Notation
The “O” stands for “order of,” describing the upper‑bound (worst‑case) growth rate of an algorithm’s time or space requirements as the input size n increases.
Computing Time Complexity
Identify the Input
Determine what constitutes the input and denote its size, commonly n.
function sumArray(arr) {
let sum = 0;
for (let i = 0; i < arr.length; i++) {
sum += arr[i];
}
}Here, n = arr.length.
Count the Operations Inside Loops
Focus on the most repeated operations.
Simple for loop
for (let i = 0; i < n; i++) {
// ...
}→ O(n)
Nested loops
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
// ...
}
}→ O(n²)
Loop with input halving (binary search pattern)
while (low <= high) {
mid = Math.floor((low + high) / 2);
// ...
}→ O(log n)
Recursive calls (e.g., factorial)
function factorial(n) {
if (n === 0) return 1;
return n * factorial(n - 1);
}→ O(n) (the factorial function itself is linear in the number of recursive calls; the “n log n” label in the original text was a mistake)
Simplifying Expressions
O(3n + 10)→ O(n)O(n² + n)→ O(n²)
Common Time Complexities
| Complexity | Description |
|---|---|
| O(1) | Constant time – execution time does not depend on input size. |
| O(log n) | Logarithmic – typical of binary search; the problem size is halved each step. |
| O(n) | Linear – a single pass over the input. |
| O(n log n) | Linearithmic – common in efficient sorting algorithms (e.g., mergesort, heapsort). |
| O(n²) | Quadratic – nested loops over the same input size. |
| O(n³) | Cubic – three nested loops. |
| O(2ⁿ) | Exponential – each element generates two recursive calls (e.g., naive recursive Fibonacci). |
| O(n!) | Factorial – permutations of the input (e.g., brute‑force traveling salesman). |
Ordered List of Complexities (Fastest → Slowest)
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)Understanding time complexity is essential for writing efficient and scalable code. By using Big‑O notation, you can analyze how an algorithm’s performance changes with input size and make informed decisions about which approach to use. Keep these complexities in mind as you design and optimize your programs.