Big-O, Big-Ω and Θ: definitions with constants

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Maximum edges of a simple undirected graph on n vertices? from Lesson 0.2.3
• 1 + 2 + … + n = ? from Lesson 0.1.2
• How many times does a loop that doubles i from 1 to n run? from Lesson 0.1.2

1 · The Hook

🎣

Algorithm X takes 3n² + 5n + 2 steps; algorithm Y takes 1000n log n. For small n, X is faster; for large n, Y wins by miles. Exact step counts are messy and machine-dependent; what matters is how they grow. Asymptotic notation keeps the growth and throws away the clutter. Every GATE complexity question is written in it.

2 · Predict First

🤔

For n = 10, 3n² + 5n + 2 = 352 and 4n² = 400. Is 3n² + 5n + 2 ≤ 4n² for every n ≥ 10? What does that say about how fast 3n² + 5n + 2 grows?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

Yes: 4n² − (3n² + 5n + 2) = n² − 5n − 2 > 0 once n ≥ 6. So beyond a point, 3n² + 5n + 2 never exceeds a constant times n²: it grows no faster than n². In notation: 3n² + 5n + 2 = O(n²).

Big-O: an upper bound

f(n) = O(g(n)) if there exist constants c > 0 and n₀ such that f(n) ≤ c·g(n) for all n ≥ n₀. "Eventually, f is at most a constant times g."

Big-Ω: a lower bound

f(n) = Ω(g(n)) if there exist c > 0 and n₀ with f(n) ≥ c·g(n) for all n ≥ n₀.

Θ: a tight bound

f(n) = Θ(g(n)) if f = O(g) and f = Ω(g): there are c₁, c₂ > 0 and n₀ with c₁·g(n) ≤ f(n) ≤ c₂·g(n) for all n ≥ n₀.

Worked proof

3n² + 5n + 2 = Θ(n²):

• Upper: for n ≥ 1, 3n² + 5n + 2 ≤ 3n² + 5n² + 2n² = 10n² → c₂ = 10, n₀ = 1.
• Lower: 3n² + 5n + 2 ≥ 3n² for all n ≥ 1 → c₁ = 3.

Working rules

• Drop constant factors: 7n³ = Θ(n³); log₁₀ n = Θ(log n) (bases differ by a constant, Lesson 0.1.2).
• Keep the dominant term: a polynomial of degree d is Θ(nᵈ). f + g = Θ(max(f, g)).
• Products multiply: Θ(f)·Θ(g) = Θ(f·g).
• O is only an upper bound: n = O(n²) and n = O(2ⁿ) are true (but not tight). Ω is only a lower bound.
• Saying "the running time is O(n²)" means it never grows faster than n²; "Θ(n²)" means exactly that growth.

4 · Visual

c2*g(n)
   f(n)   ____/
        _/  ____ f(n)            for n >= n0 the curve f stays between c1*g and c2*g
       / __/   ____ c1*g(n)        -> f = Theta(g)
    __/_/ ____/
   |------|----------------> n
         n0

5 · Worked Examples

Example 1 Easy

Give Θ for f(n) = 6n³ + 100n² + 50.

Solution

Θ(n³): keep the dominant term, drop the constant.

Example 2 Medium

Find a constant c that shows 2n + 7 = O(n) with n₀ = 7.

Solution

For n ≥ 7, 7 ≤ n, so 2n + 7 ≤ 3n: c = 3 works.

Example 3 GATE

Is 3ⁿ = O(2ⁿ)?

Solution

No. 3ⁿ / 2ⁿ = (1.5)ⁿ grows without bound, so no constant c can make 3ⁿ ≤ c·2ⁿ for all large n.

6 · GATE Traps

⚠️

• O(g) is an upper bound: "O(n²)" does not mean the time is about n².
• Constant factors in the exponent matter: 2²ⁿ ≠ O(2ⁿ); constant factors in front do not.
• Log bases do not matter inside Θ; exponent bases do (2ⁿ vs 3ⁿ).
• The definitions need the inequality only for all n ≥ n₀, not for all n.

7 · Memory Hook

🧠

"O caps it, Ω floors it, Θ pins it."

8 · Connect the Dots

This lesson defined O, Ω and Θ. Next: their strict cousins o and ω, and the skill GATE tests most: putting a list of functions in order of growth.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markΘ of a polynomial

4n² + 3n log n + 7 is:

• (A) Θ(log n)
• (B) Θ(n log n)
• (C) Θ(n²)
• (D) Θ(n³)

Q2MSQ2 marksTrue statements

Which are true?

• (A) 2ⁿ⁺⁵ = Θ(2ⁿ)
• (B) n³ = O(n⁴)
• (C) n⁴ = O(n³)
• (D) log₃ n = Θ(log₂ n)

Q3NAT1 markConstant

Find the smallest integer c such that 5n + 20 ≤ c·n for all n ≥ 10.

Numerical answer: ________

Q4MCQ1 markExponential bases

Which is false?

• (A) 2ⁿ = O(3ⁿ)
• (B) 3ⁿ = Ω(2ⁿ)
• (C) 2ⁿ = O(2²ⁿ)
• (D) 2²ⁿ = O(2ⁿ)

Q5MCQ1 markMeaning

"The worst-case running time of algorithm A is O(n log n)" means:

• (A) A always takes exactly about n log n steps
• (B) A is optimal
• (C) A never takes more than a constant times n log n steps for large n
• (D) A takes at least n log n steps

10 · Rule Card

• O: f ≤ c·g eventually. Ω: f ≥ c·g eventually. Θ: both.
• Drop constant factors and lower-order terms; polynomial degree d → Θ(nᵈ).
• Log bases don't matter; exponential bases and exponent constants do.
• O and Ω need not be tight.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

asymptotic notationBig-OBig-ΩΘconstants c and n₀dominant termupper vs tight bound

12 · Answer Vault