Algorithm Analysis Deep Dive
Master Big-O, Big-Omega, and Big-Theta notation to analyze algorithm efficiency rigorously.
What you'll learn
- Formal definition of Big-O, Big-Omega, Big-Theta
- How to prove asymptotic bounds from first principles
- Common complexity classes and their growth rates
- Amortized analysis for sequences of operations
Concept
Algorithm Analysis Deep Dive
Asymptotic notation gives us a language for describing how an algorithm's resource usage grows as the input grows. The three most important notations are Big-O (upper bound), Big-Omega (lower bound), and Big-Theta (tight bound). Formally, f(n) = O(g(n)) means there exist positive constants c and n0 such that 0 <= f(n) <= c*g(n) for all n >= n0.
Proving Bounds
To prove f(n) = O(g(n)), you find constants c and n0 and show the inequality holds. For example, to show 3n^2 + 5n + 7 = O(n^2), pick c = 15 and n0 = 1: for n >= 1, 3n^2 + 5n + 7 <= 15n^2. The art is choosing n0 large enough that lower-order terms are dominated.
Complexity Class Hierarchy
From slowest to fastest: O(1) < O(log n) < O(sqrt(n)) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(2^n) < O(n!). An O(n log n) algorithm is dramatically faster than O(n^2) on large inputs.
Amortized Analysis
Some operations are occasionally expensive but cheap on average. A dynamic array append is O(1) amortized even though resizing is O(n) because resizes happen rarely. The aggregate method sums all costs and divides by n.
Example
// Proving 3n^2 + 5n + 7 = O(n^2) empirically
function f(n) { return 3*n*n + 5*n + 7; }
function g(n) { return n*n; }
let c = 15, n0 = 1, holds = true;
for (let n = n0; n <= 100000; n++) {
if (f(n) > c * g(n)) { holds = false; break; }
}
console.log(`Bound holds: ${holds}`);
// Amortized: dynamic array append
class DynamicArray {
constructor() { this.arr = new Array(1); this.size = 0; }
append(x) {
if (this.size === this.arr.length) {
const newArr = new Array(this.arr.length * 2);
for (let i = 0; i < this.size; i++) newArr[i] = this.arr[i];
this.arr = newArr;
}
this.arr[this.size++] = x;
}
}
const da = new DynamicArray();
for (let i = 0; i < 100; i++) da.append(i);
console.log('Capacity:', da.arr.length, 'Size:', da.size);
The first part verifies the Big-O bound empirically. The DynamicArray shows amortized O(1) append - resizes double capacity, so each element is copied at most once per doubling.
Try it
- Code Diff
Compare two algorithm implementations to see how complexity affects real performance.
Common mistakes
The mistake
Confusing Big-O (upper bound) with Big-Theta (tight bound).
The fix
Big-O only says no worse than. An O(n) algorithm is also O(n^2). Use Big-Theta when you mean exactly this growth rate.
The mistake
Forgetting constants in amortized analysis.
The fix
Amortized O(1) means the total cost of n operations is O(n), not that every single operation is O(1).
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.