---
title: "Show n(n-1)/2 is Theta(n^2)"
subject: "Data Structure and Algorithm"
chapter: 9
key: "semester_4/data_structure_and_algorithm:half-n-n-minus-1-theta"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/half-n-n-minus-1-theta
site: BCT Engineering
---

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

Data Structure and Algorithm · Chapter 9: Growth Functions

- Asked in: 2071 Bhadra, 3 marks; 2070 Magh, 2 marks (asked 2 times)
- Video: [Big Omega and Big Theta Notations (Solved Problems)](https://www.youtube.com/watch?v=-uO5ngF9WuY) — Neso Academy
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/half-n-n-minus-1-theta
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-9

## Question

Show whether the following assertion is true or false, justify: 1/2 n(n-1) ∈ Θ(n²)

## Short answer

True. Expand ½n(n−1) = ½n²−½n. For n≥2, ½n²−½n ≤ ½n² (c₂=½) and ½n²−½n ≥ ¼n² (c₁=¼). Thus ¼n² ≤ ½n(n−1) ≤ ½n², proving Θ(n²). Limit: lim (½n(n−1))/n² = ½, a positive constant.

## Answer

**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²).

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. Is 1/2 n(n-1) in Theta(n^2)?
   A. True
   B. False, it is Theta(n)
   C. False, it is Theta(n^3)
   D. Cannot be decided
   Answer: A. It is bounded between n^2/4 and n^2/2 for n >= 2. (Key point: Verdict)

2. What upper bound constant c2 is used?
   A. 1/4
   B. 1/2, since n^2/2 - n/2 <= n^2/2
   C. 2
   D. 1
   Answer: B. Subtracting n/2 only lowers the value. (Key point: Upper bound constant)

3. For n >= 2, which inequality gives the lower bound 1/4 n^2?
   A. n/2 >= n^2/4
   B. n <= 1
   C. n/2 <= n^2/4
   D. n^2 <= n
   Answer: C. Then n^2/2 - n/2 >= n^2/2 - n^2/4 = n^2/4. (Key point: Lower bound step)

4. What does the limit test give for [n(n-1)/2] / n^2?
   A. 0
   B. Infinity
   C. 1
   D. 1/2, a positive constant
   Answer: D. A positive finite limit proves Theta(n^2). (Key point: Limit method)

## Related in other subjects

- [True/false: derivative controllers always used with others](https://www.bctengineer.com/question.md?key=semester_3%2Fcontrol_systems%3Aderivative-always-with-others) — Control Systems, chapter 7, asked 3×
- [True/false: CT secondary kept open](https://www.bctengineer.com/question.md?key=semester_4%2Felectrical_machine%3Atf-false-ct-secondary-open) — Electrical Machine, chapter 2
- [True/false: series motor started at no load](https://www.bctengineer.com/question.md?key=semester_4%2Felectrical_machine%3Atf-dc-series-motor-start-noload) — Electrical Machine, chapter 4
- [True/false: rotor core loss neglected](https://www.bctengineer.com/question.md?key=semester_4%2Felectrical_machine%3Atf-rotor-core-loss-neglected) — Electrical Machine, chapter 5