Algorithmic Foundations
Analyzing Algorithms
Asymptotic notation — O, Ω, and Θ — describes how running time or memory grows as input size n grows, stripped of machine-specific constants. It lets you compare algorithms, not benchmarks.
O(f(n))is an upper bound on growth;Ω(f(n))a lower bound;Θ(f(n))means both match — the tight bound- Constants and low-order terms are dropped:
3n² + 100n + 5isΘ(n²) - Worst case is the default lens; average case and best case need to be stated explicitly
- Common orders, cheapest to priciest:
O(1),O(log n),O(n),O(n log n),O(n²),O(2ⁿ) - Define n precisely — number of elements, bits, vertices + edges — before quoting a bound
- A bound describes a trend for large n; it says nothing about which algorithm wins at n = 10
| Order | Name | Operations at n = 10⁶ |
|---|---|---|
O(log n) | Logarithmic | ~20 |
O(n) | Linear | 1,000,000 |
O(n log n) | Linearithmic | ~20,000,000 |
O(n²) | Quadratic | 10¹² |
O(2ⁿ) | Exponential | unfathomable |
Asymptotic analysis counts the dominant operation — comparisons in a sort, array accesses in a scan — as a function of input size, then asks how that count scales. It deliberately ignores constant factors and hardware, because those change with every machine and every JIT warm-up; what does not change is that a Θ(n²) algorithm will eventually lose to a Θ(n log n) one as n grows, no matter how well-tuned the constant is.
static boolean hasDuplicateLinear(int[] a) { // O(n) extra space, O(n) time
Set<Integer> seen = new HashSet<>();
for (int x : a) {
if (!seen.add(x)) return true; // O(1) amortized per check
}
return false;
}
static boolean hasDuplicateQuadratic(int[] a) { // O(1) extra space, O(n^2) time
for (int i = 0; i < a.length; i++) {
for (int j = i + 1; j < a.length; j++) {
if (a[i] == a[j]) return true; // n*(n-1)/2 comparisons
}
}
return false;
}