---
title: "Omega and Theta notation with example"
subject: "Data Structure and Algorithm"
chapter: 9
key: "semester_4/data_structure_and_algorithm:omega-theta-notation-example"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/omega-theta-notation-example
site: BCT Engineering
---

# Omega and Theta notation with example

Data Structure and Algorithm · Chapter 9: Growth Functions

- Asked in: 2073 Bhadra, 4 marks; 2072 Asoj, 4 marks; 2070 Bhadra, 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/omega-theta-notation-example
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-9

## Question

Define Omega and Theta notation with suitable example.

## Short answer

Ω(g(n)) is an asymptotic lower bound: f(n) ≥ c·g(n) for n ≥ n₀, e.g., 3n+2 = Ω(n). Θ(g(n)) is a tight bound: c₁·g(n) ≤ f(n) ≤ c₂·g(n) for n ≥ n₀, e.g., 3n+2 = Θ(n) with c₁=3, c₂=4 for n≥2.

## Answer

#### 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 gives an asymptotic **lower bound** (best-case type guarantee).
```text
 time
  |          f(n)
  |        .
  |      .    ___ c*g(n)
  |    .  ___/
  |  .___/
  |_/__________________ n
       n0
   f(n) >= c*g(n) for n >= n0
```
Example: f(n) = 3n + 2. Since 3n + 2 ≥ 3n for all n ≥ 1, f(n) = Ω(n) with c = 3, n₀ = 1.

#### 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₀. The function is bounded above and below by g(n); that is, f(n) = O(g(n)) and f(n) = Ω(g(n)).
```text
 time
  |            c2*g(n)
  |          /
  |        /  f(n)
  |      / . '
  |    / .'     c1*g(n)
  |  /.' ____--
  |_/'--________________ n
      n0
```
Example: f(n) = 3n + 2. For n ≥ 2: 3n ≤ 3n + 2 ≤ 4n, so c₁ = 3, c₂ = 4, n₀ = 2 and f(n) = Θ(n).

Another example: n²/2 + 3n = Θ(n²) but is not Θ(n³) (it is O(n³) only loosely).

## Check yourself

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

1. What does f(n) = Omega(g(n)) mean?
   A. f(n) <= c*g(n) for all n >= n0
   B. c1*g(n) <= f(n) <= c2*g(n)
   C. f(n) >= c*g(n) for all n >= n0
   D. f(n)/g(n) tends to 0
   Answer: C. Omega is an asymptotic lower bound. (Key point: Omega definition)

2. What makes Theta a tight bound?
   A. f is bounded only above by g
   B. f equals g exactly for all n
   C. f is smaller than g for all n
   D. f is bounded both above and below by multiples of g
   Answer: D. Theta requires c1*g <= f <= c2*g, i.e. f = O(g) and f = Omega(g). (Key point: Theta definition)

3. Which constants prove 3n + 2 = Theta(n)?
   A. c1 = 3, c2 = 4, n0 = 2
   B. c1 = 1, c2 = 2, n0 = 5
   C. c1 = 4, c2 = 3, n0 = 2
   D. c1 = 3, c2 = 3, n0 = 1
   Answer: A. 3n <= 3n+2 <= 4n holds for n >= 2. (Key point: Constants for 3n+2)

4. Is n^2/2 + 3n = Theta(n^3)?
   A. Yes, since it is O(n^3)
   B. No, it is only loosely O(n^3)
   C. Yes, because n^3 is larger
   D. Only for n < 3
   Answer: B. Theta needs a lower bound too, which n^3 cannot give. (Key point: Theta vs loose O)

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