Show n(n-1)/2 is Theta(n^2)

The assertion is true.

We must find positive constants c₁, c₂, n₀ with c₁n² ≤ ½n(n−1) ≤ c₂n² for all n ≥ n₀.

½n(n−1) = ½n² − ½n.

Upper bound

½n² − ½n ≤ ½n² for all n ≥ 0, so c₂ = ½.

Lower bound

For n ≥ 2, ½n ≤ ¼n² (because n ≥ 2 gives n/2 ≤ n²/4). Then ½n² − ½n ≥ ½n² − ¼n² = ¼n². So c₁ = ¼.

Check at n = 2: ½·2·1 = 1, and ¼·4 = 1 ≤ 1 ≤ ½·4 = 2. It holds.

Hence ¼n² ≤ ½n(n−1) ≤ ½n² for all n ≥ 2 (c₁ = ¼, c₂ = ½, n₀ = 2), so ½n(n−1) ∈ Θ(n²).

Using limits: lim (n→∞) [½n(n−1)]/n² = ½, a positive constant, which also proves Θ(n²).