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

# Big-O and Big-Omega with curves

Data Structure and Algorithm · Chapter 9: Growth Functions

- Asked in: 2074 Bhadra, 5 marks
- Video: [L-1.3: Asymptotic Notations | Big O | Big Omega | Theta Notations | Most Imp Topic Of Algorithm](https://www.youtube.com/watch?v=7dz8Iaf_weM) — Gate Smashers
- 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-big-omega-curves
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-9

## Question

Define big-O notation and Big-Omega notation with their respective curves.

## Short answer

Big-O: f(n) ≤ c·g(n) for n ≥ n₀, an upper bound (e.g., 5n+3 = O(n)). Big-Omega: f(n) ≥ c·g(n) for n ≥ n₀, a lower bound (e.g., 5n+3 = Ω(n)). They describe worst-case and best-case growth respectively.

## Answer

#### Big-O notation
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 gives an asymptotic **upper bound**: f grows no faster than g.
```text
 time
  |           c*g(n)
  |          /
  |         /  . f(n)
  |        / .
  |       /.
  |______/._____________ n
        n0
```
Example: 5n + 3 ≤ 6n for n ≥ 3, so 5n + 3 = O(n).

#### Big-Omega notation
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**: f grows at least as fast as g.
```text
 time
  |          f(n)
  |        .
  |      .    ___ c*g(n)
  |    .  ___/
  |  .___/
  |_/__________________ n
       n0
```
Example: 5n + 3 ≥ 5n for n ≥ 1, so 5n + 3 = Ω(n).

## Check yourself

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

1. Which defines f(n) = O(g(n))?
   A. f(n) <= c*g(n) for all n >= n0
   B. f(n) >= c*g(n) for all n >= n0
   C. f(n) = g(n)
   D. f(n) < g(n) for all n
   Answer: A. c and n0 are positive constants. (Key point: Big O definition)

2. On the Omega graph, how does f lie relative to c*g(n) after n0?
   A. Below it
   B. Above it
   C. Equal to it
   D. Crossing it repeatedly
   Answer: B. Omega is a lower bound so f >= c*g. (Key point: Omega curve)

3. Which pair proves 5n + 3 = O(n)?
   A. 5n+3 >= 5n for n >= 1
   B. 5n+3 <= 5n
   C. 5n+3 <= 6n for n >= 3
   D. 5n+3 <= n
   Answer: C. c = 6, n0 = 3 gives the upper bound. (Key point: 5n+3)

## Close variants set in other exams

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

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