---
title: "Define Big O, Omega and Theta"
subject: "Data Structure and Algorithm"
chapter: 9
key: "semester_4/data_structure_and_algorithm:big-o-omega-theta-define"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/big-o-omega-theta-define
site: BCT Engineering
---

# Define Big O, Omega and Theta

Data Structure and Algorithm · Chapter 9: Growth Functions

- Asked in: 2072 Magh, 4 marks; 2069 Poush, 4 marks; 2068 Magh, 4 marks (asked 3 times)
- Video: [1.8.1 Asymptotic Notations Big Oh - Omega - Theta #1](https://www.youtube.com/watch?v=A03oI0znAoc) — 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-omega-theta-define
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-9

## Question

Define Big O, Big Omega and Big Theta notation (with their respective curves).

## Short answer

Big O: f(n) ≤ c·g(n) for n ≥ n₀ (upper bound). Big Omega: f(n) ≥ c·g(n) for n ≥ n₀ (lower bound). Big Theta: c₁·g(n) ≤ f(n) ≤ c₂·g(n) for n ≥ n₀ (tight bound). Example: 3n+2 = Θ(n).

## Answer

#### Big O notation (upper bound)
f(n) = O(g(n)) if there exist positive constants c and n₀ such that f(n) ≤ c·g(n) for all n ≥ n₀. It states that f grows no faster than g (worst case guarantee).
```text
 time
  |           c*g(n)
  |          /
  |         /  . f(n)
  |        / .
  |       /.
  |______/._____________ n
        n0
```
Example: 3n + 2 ≤ 4n for n ≥ 2, so 3n + 2 = O(n).

#### Big Omega notation (lower bound)
f(n) = Ω(g(n)) if there exist positive constants c and n₀ such that f(n) ≥ c·g(n) for all n ≥ n₀. It states that f grows at least as fast as g.
```text
 time
  |          f(n)
  |        .
  |      .    ___ c*g(n)
  |    .  ___/
  |  .___/
  |_/__________________ n
       n0
```
Example: 3n + 2 ≥ 3n for n ≥ 1, so 3n + 2 = Ω(n).

#### Big Theta notation (tight bound)
f(n) = Θ(g(n)) if there exist positive constants c₁, c₂ and n₀ such that c₁·g(n) ≤ f(n) ≤ c₂·g(n) for all n ≥ n₀. Equivalent to f = O(g) and f = Ω(g).
```text
 time
  |            c2*g(n)
  |          /
  |        /  f(n)
  |      / . '
  |    / .'     c1*g(n)
  |  /.' ____--
  |_/'--________________ n
      n0
```
Example: 3n ≤ 3n + 2 ≤ 4n for n ≥ 2, so 3n + 2 = Θ(n).

## Check yourself

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

1. What does Big O express?
   A. A lower bound
   B. An exact bound
   C. An upper bound: f grows no faster than g
   D. Average case only
   Answer: C. f(n) <= c*g(n) for n >= n0. (Key point: Big O meaning)

2. Which pair shows 3n+2 = Omega(n)?
   A. 3n+2 <= 4n for n >= 2
   B. 3n+2 >= n^2
   C. 3n+2 <= 3n
   D. 3n+2 >= 3n for n >= 1
   Answer: D. Omega needs a lower bound c*g(n), here c = 3. (Key point: Omega example)

3. How is Theta related to O and Omega?
   A. f = Theta(g) iff f = O(g) and f = Omega(g)
   B. Theta is O or Omega
   C. Theta is the same as O
   D. Theta is the average of O and Omega
   Answer: A. Theta is tight when both bounds hold. (Key point: Theta relation)

## Close variants set in other exams

- [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×

## Related in Data Structure and Algorithm

- [Omega and Theta notation with example](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aomega-theta-notation-example) — Data Structure and Algorithm, chapter 9, asked 3×
- [Importance of growth function; Theta, O, Omega](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Agrowth-function-importance) — Data Structure and Algorithm, chapter 9
- [Big-O notation with properties](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abig-o-properties) — Data Structure and Algorithm, chapter 9