6 Practice Proof Examples

Below are 6 Big O proof examples with detailed, easy-to-follow explanations. Every step is broken down so you’ll know exactly what’s happening.

Example 1: Prove 4n + 2 ∈ O(n)

Step 1: Start with the inequality

4n + 2 ≤ c × n

Step 2: Subtract 4n from both sides

(4n + 2) - 4n ≤ (c × n) - 4n
→ 2 ≤ (c - 4)n

Step 3: Solve for C

2 ≤ (c - 4)n
→ 2 / n ≤ c - 4
→ c ≥ 4 + (2 / n)

Step 4: Try a value like n = 2