---
title: "Big-O notation with properties"
subject: "Data Structure and Algorithm"
chapter: 9
key: "semester_4/data_structure_and_algorithm:big-o-properties"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/big-o-properties
site: BCT Engineering
---

# Big-O notation with properties

Data Structure and Algorithm · Chapter 9: Growth Functions

- Asked in: 2071 Magh, 3 marks
- Video: [1.9 Properties of Asymptotic Notations](https://www.youtube.com/watch?v=NI4OKSvGAgM) — Abdul Bari
- 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/big-o-properties
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-9

## Question

Explain big-O notation with its properties.

## Short answer

Big-O: f(n) ≤ c·g(n) for large n. Properties: reflexivity (f = O(f)), transitivity, constant factors absorbed, sum rule (O(max(g₁,g₂))), product rule, polynomial order, and growth hierarchy O(1) ⊂ O(log n) ⊂ O(n) ⊂ O(n log n) ⊂ O(n²) ⊂ O(2ⁿ).

## Answer

**Big-O notation:** f(n) = O(g(n)) if there are positive constants c and n₀ with f(n) ≤ c·g(n) for all n ≥ n₀. It gives an upper bound on the growth rate. Example: 2n + 10 ≤ 3n for n ≥ 10, so 2n + 10 = O(n).

#### Properties
1. **Reflexivity:** f(n) = O(f(n)).
2. **Transitivity:** if f = O(g) and g = O(h), then f = O(h).
3. **Constant factor:** O(c·f(n)) = O(f(n)) for c > 0.
4. **Sum rule:** if f₁ = O(g₁) and f₂ = O(g₂), then f₁ + f₂ = O(max(g₁, g₂)).
5. **Product rule:** f₁ · f₂ = O(g₁ · g₂).
6. **Polynomial:** if f(n) = aₖnᵏ + ... + a₁n + a₀, then f(n) = O(nᵏ).
7. If f(n) ≤ g(n) for all large n, then O(f) ⊆ O(g).
8. Growth order: O(1) ⊂ O(log n) ⊂ O(n) ⊂ O(n log n) ⊂ O(n²) ⊂ O(2ⁿ).

## Check yourself

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

1. If f = O(g) and g = O(h), then?
   A. h = O(f)
   B. f = Omega(h)
   C. f = O(h)
   D. Nothing can be said
   Answer: C. Transitivity of O. (Key point: Transitivity)

2. If f1 = O(g1) and f2 = O(g2), then f1 + f2 is?
   A. O(g1 * g2)
   B. O(min(g1, g2))
   C. O(g1 - g2)
   D. O(max(g1, g2))
   Answer: D. The faster-growing term dominates. (Key point: Sum rule)

3. A polynomial of degree k is?
   A. O(n^k)
   B. O(k)
   C. O(n^(k+1)) only
   D. O(2^n) only
   Answer: A. The highest-degree term dominates. (Key point: Polynomial rule)

## Related in Data Structure and Algorithm

- [Define Big O, Omega and Theta](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abig-o-omega-theta-define) — Data Structure and Algorithm, chapter 9, asked 4×
- [Big-O and Big-Omega with curves](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abig-o-big-omega-curves) — Data Structure and Algorithm, chapter 9, asked 4×
- [Big-Oh significance and limitation](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abig-oh-significance-limitation) — Data Structure and Algorithm, chapter 9