Home / Courses / Discrete Mathematics / Unit 9

Discrete Mathematics Unit 9: Algorithms & complexity (intro)

Big-O notation describes how an algorithm's running time grows as input size grows, ignoring constants.

Covers: Big-O, basic algorithm analysis

Study guide

Algorithm analysis measures how running time or memory grows with input size n. Big-O notation describes an upper bound on growth: f(n) is O(g(n)) if there are constants C and k with f(n) ≤ C·g(n) for all n > k. Constants and lower-order terms don't matter, so 3n² + 5n + 7 is O(n²). Big-Omega gives a lower bound, and Big-Theta means both bounds match.

Common growth rates, from slowest to fastest: constant O(1), logarithmic O(log n), linear O(n), linearithmic O(n log n), quadratic O(n²), cubic O(n³), exponential O(2ⁿ), and factorial O(n!). Exponential and factorial algorithms become impractical even for modest n, while any polynomial is eventually dwarfed by 2ⁿ.

Basic analysis counts operations. A single loop over n items is O(n); two nested loops over n items are O(n²); a loop that halves the problem each time is O(log n). Linear search is O(n), while binary search on a sorted list is O(log n) because it halves the search range each step. Simple sorts like bubble sort and insertion sort are O(n²) in the worst case, while merge sort is O(n log n).

Worst-case analysis gives guarantees, while average-case analysis describes typical behavior. Recursive algorithms are analyzed with recurrence relations, like T(n) = 2T(n/2) + n for merge sort, which solves to O(n log n).

f is o(g) if f(n)/g(n) → 0, so f grows strictly slower than g, and f is ω(g) if the ratio → ∞. f ~ g means the ratio → 1. Little-o implies big-O, but not the other way around: n/100 is O(n) but not o(n). Stirling's formula says n! ~ √(2πn)(n/e)ⁿ. It shows that n! grows faster than any cⁿ but is o(nⁿ). It also gives log(n!) = Θ(n log n).

For a decreasing positive function f, ∫₁ⁿ⁺¹ f(x) dx ≤ f(1) + f(2) + … + f(n) ≤ f(1) + ∫₁ⁿ f(x) dx. For example, the harmonic sum Hₙ = 1 + 1/2 + … + 1/n is ~ ln n.

Key ideas

• f(n) = O(g(n)) means f grows no faster than a constant times g for large n.
• Keep only the fastest-growing term and drop constants.
• Common orders: 1 < log n < n < n log n < n² < 2ⁿ < n!.
• Nested loops over n items usually give O(n²).
• Binary search is O(log n); linear search is O(n).

Formulas and rules

Common mistakes

• Keeping constants or lower-order terms in a big-O answer.
• Assuming O(n²) is always slower than O(n) for small inputs.

Words to know

Big-O simplification

Keep the fastest-growing term and drop constants: 3n² + 5n + 7 is O(n²).

Running time of binary search

O(log n)

Exponential vs. polynomial growth

2ⁿ eventually outgrows any polynomial like n¹⁰⁰.

Typical cost of two nested loops over n items

O(n²)

Big-O notation

f = O(g): for large n, f(n) ≤ C·g(n).

Common growth rates

1 < log n < n < n log n < n² < 2ⁿ < n!

Algorithm

A finite sequence of precise steps for solving a problem.

Big-Omega (Ω)

A lower bound on growth.

Big-Theta (Θ)

Matching upper and lower bounds.

Linear search

O(n): checks items one by one.

Merge sort

O(n log n) divide-and-conquer sort.

Worst-case analysis

The maximum number of operations over all inputs of size n.

Merge sort recurrence

T(n) = 2T(n/2) + n → O(n log n)

Sample practice questions

17 more questions like these, from level 1 to 5, are in the practice set.