Unit X: Growth Functions (Asymptotic Notations) — 2 Hrs.
Data Structures & Algorithms — Complete Detailed Chapter Notes
Full descriptions with graphs, formal definitions, and step-by-step calculated examples for each notation. Ends with fully-answered important questions (2 / 6 / 10 marks).
Table of Contents
- Introduction to Asymptotic Notations
- Big-O Notation (Upper Bound)
- Omega Notation (Lower Bound)
- Theta Notation (Tight Bound)
- Limitations of Big-O Notation
- Important Questions with Full Answers
10.1 Introduction to Asymptotic Notations
When we design an algorithm, we need a way to measure how efficient it is — how its running time (or memory use) grows as the size of the input grows. Measuring the exact time in seconds is not useful, because it depends on the computer's speed, the programming language, the compiler, and other running programs. Instead, we measure the rate of growth of the work done as the input size n increases.
Asymptotic notation is the mathematical language used to describe this rate of growth as n → ∞ (n becomes very large). "Asymptotic" means we care about the behaviour for large inputs, ignoring small ones.
Why we ignore constants and lower-order terms
Consider an algorithm whose exact running time is:
T(n) = 3n² + 5n + 100
As n grows large, the term 3n² completely dominates the others:
| n | 3n² | 5n | 100 | Which dominates? |
|---|---|---|---|---|
| 10 | 300 | 50 | 100 | 3n² |
| 100 | 30,000 | 500 | 100 | 3n² (by far) |
| 1000 | 3,000,000 | 5,000 | 100 | 3n² (overwhelmingly) |
So we keep only the dominant term and drop the constant multiplier, giving the growth class O(n²). This is the core idea of asymptotic analysis: keep the fastest-growing term, drop constants and lower-order terms.
The curve f(n) = 3n² + 2n + 1 hugs the pure 3n² curve as n grows — the lower-order terms become negligible, so the growth class is O(n²).
The three asymptotic notations
| Notation | Symbol | Bound it gives | Case it usually describes |
|---|---|---|---|
| Big-O | O | Upper bound (at most) | Worst case |
| Omega | Ω | Lower bound (at least) | Best case |
| Theta | Θ | Tight bound (both) | Exact growth |
Common growth functions, from slowest-growing to fastest-growing
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)
| Growth | Name | Example |
|---|---|---|
| O(1) | Constant | Accessing arr[i] |
| O(log n) | Logarithmic | Binary search |
| O(n) | Linear | Linear search |
| O(n log n) | Linearithmic | Merge sort, Quick sort (avg) |
| O(n²) | Quadratic | Bubble / Selection sort |
| O(2ⁿ) | Exponential | Naïve recursive Fibonacci |
The graph makes the practical message clear: an O(2ⁿ) algorithm explodes almost immediately, O(n²) grows fast, while O(log n) and O(1) stay nearly flat — which is why we always prefer lower growth classes for large inputs.
10.2 Big-O Notation (Upper Bound)
Meaning
Big-O gives the upper bound on an algorithm's growth — it tells us the algorithm will take at most this much time. It answers: "In the worst case, how fast does the work grow?" Because it guarantees the work will never grow faster than the stated function, Big-O is the most widely used notation.
Formal definition
f(n) = O(g(n)) if there exist positive constants c and n₀ such that 0 ≤ f(n) ≤ c · g(n) for all n ≥ n₀.
In words: beyond some input size n₀, the function f(n) never rises above a constant multiple (c) of g(n).
The blue curve f(n) = 2n + 3 stays below the red curve c·g(n) = 3n for every n ≥ 3. So c = 3 and n₀ = 3 witness that f(n) = O(n).
Step-by-step Example 1 — show that f(n) = 2n + 3 is O(n)
Goal: find constants c and n₀ so that 2n + 3 ≤ c·n for all n ≥ n₀.
Step 1 — Set up the inequality. We want 2n + 3 ≤ c·n.
Step 2 — Bound the lower-order term by the dominant term. For n ≥ 3, we know 3 ≤ n. Therefore:
2n + 3 ≤ 2n + n = 3n.
Step 3 — Read off the constants. The inequality 2n + 3 ≤ 3n holds for all n ≥ 3. So choose c = 3 and n₀ = 3.
Step 4 — Conclusion. Since positive c and n₀ exist, 2n + 3 = O(n). ✔
Step-by-step Example 2 — show that f(n) = 3n² + 2n + 1 is O(n²)
Step 1 — Setup. We want 3n² + 2n + 1 ≤ c·n².
Step 2 — Replace each term with an n² term (valid for n ≥ 1).
3n² = 3n²2n ≤ 2n²(sincen ≤ n²for n ≥ 1)1 ≤ 1n²(since1 ≤ n²for n ≥ 1)
Step 3 — Add them up. 3n² + 2n + 1 ≤ 3n² + 2n² + n² = 6n².
Step 4 — Read off constants. The inequality holds for all n ≥ 1, so c = 6 and n₀ = 1.
Step 5 — Conclusion. 3n² + 2n + 1 = O(n²). ✔
How to find Big-O quickly (shortcut)
- Drop all lower-order terms (keep only the fastest-growing term).
- Drop the constant coefficient of that term.
Example: T(n) = 5n³ + 100n² + 20 → keep 5n³ → drop 5 → O(n³).
10.3 Omega Notation (Lower Bound)
Meaning
Omega gives the lower bound on an algorithm's growth — it tells us the algorithm takes at least this much time. It answers: "In the best case, how fast does the work grow, at minimum?"
Formal definition
f(n) = Ω(g(n)) if there exist positive constants c and n₀ such that 0 ≤ c · g(n) ≤ f(n) for all n ≥ n₀.
In words: beyond some input size n₀, f(n) never falls below a constant multiple of g(n).
The blue curve f(n) = 2n + 3 always stays above the red curve c·g(n) = 2n. So c = 2 and n₀ = 1 witness that f(n) = Ω(n).
Step-by-step Example 1 — show that f(n) = 2n + 3 is Ω(n)
Goal: find c and n₀ so that c·n ≤ 2n + 3 for all n ≥ n₀.
Step 1 — Set up the inequality. We want c·n ≤ 2n + 3.
Step 2 — Choose a simple c. Take c = 2. Then the claim becomes 2n ≤ 2n + 3.
Step 3 — Check it. 2n ≤ 2n + 3 is true for all n ≥ 1 (indeed for all n ≥ 0), because we only added 3 to the right side.
Step 4 — Conclusion. With c = 2 and n₀ = 1, we have c·n ≤ f(n), so 2n + 3 = Ω(n). ✔
Step-by-step Example 2 — show that f(n) = 3n² + 2n + 1 is Ω(n²)
Step 1 — Setup. We want c·n² ≤ 3n² + 2n + 1.
Step 2 — Choose c. Take c = 3. The claim becomes 3n² ≤ 3n² + 2n + 1.
Step 3 — Check it. 3n² ≤ 3n² + 2n + 1 is true for all n ≥ 0, because 2n + 1 ≥ 0.
Step 4 — Conclusion. With c = 3 and n₀ = 1, 3n² + 2n + 1 = Ω(n²). ✔
Practical meaning
- Linear Search best case: the key is the first element → 1 comparison → Ω(1).
- Bubble Sort best case (already sorted, optimized): one pass → Ω(n).
10.4 Theta Notation (Tight Bound)
Meaning
Theta gives the tight (exact) bound — the algorithm grows exactly at this rate, no faster and no slower. Theta is used only when the upper bound (O) and the lower bound (Ω) are the same function.
f(n) = Θ(g(n)) if and only if f(n) = O(g(n)) AND f(n) = Ω(g(n)).
Formal definition
f(n) = Θ(g(n)) if there exist positive constants c₁, c₂ and n₀ such that 0 ≤ c₁ · g(n) ≤ f(n) ≤ c₂ · g(n) for all n ≥ n₀.
In words: beyond n₀, f(n) is sandwiched between two constant multiples of g(n).
The blue curve f(n) = 2n + 3 lies between the lower line c₁·g(n) = 2n and the upper line c₂·g(n) = 3n for all n ≥ 3. So it is squeezed on both sides → Θ(n).
Step-by-step Example 1 — show that f(n) = 2n + 3 is Θ(n)
We combine the two results already proved:
Step 1 — Lower bound (Ω). From Section 10.3: 2n ≤ 2n + 3 for n ≥ 1, so with c₁ = 2 we have c₁·n ≤ f(n).
Step 2 — Upper bound (O). From Section 10.2: 2n + 3 ≤ 3n for n ≥ 3, so with c₂ = 3 we have f(n) ≤ c₂·n.
Step 3 — Combine. For all n ≥ 3:
2·n ≤ 2n + 3 ≤ 3·n, i.e. c₁·g(n) ≤ f(n) ≤ c₂·g(n).
Step 4 — Conclusion. With c₁ = 2, c₂ = 3, n₀ = 3, we get 2n + 3 = Θ(n). ✔
Step-by-step Example 2 — show that f(n) = 3n² + 2n + 1 is Θ(n²)
Step 1 — Lower bound. 3n² ≤ 3n² + 2n + 1 for n ≥ 0 → c₁ = 3 (so f = Ω(n²)).
Step 2 — Upper bound. 3n² + 2n + 1 ≤ 6n² for n ≥ 1 → c₂ = 6 (so f = O(n²)).
Step 3 — Combine. For all n ≥ 1: 3n² ≤ 3n² + 2n + 1 ≤ 6n².
Step 4 — Conclusion. With c₁ = 3, c₂ = 6, n₀ = 1, 3n² + 2n + 1 = Θ(n²). ✔
Summary of the three notations
| Notation | Relation | Meaning | Bound | Typical case |
|---|---|---|---|---|
| O(g(n)) | f(n) ≤ c·g(n) | grows no faster than g | Upper | Worst case |
| Ω(g(n)) | f(n) ≥ c·g(n) | grows no slower than g | Lower | Best case |
| Θ(g(n)) | c₁·g(n) ≤ f(n) ≤ c₂·g(n) | grows exactly like g | Tight (both) | Average/exact |
Simple analogy (marks out of 100). If your score is X:
- Big-O: "X is at most 100" — an upper limit.
- Omega: "X is at least 0" — a lower limit.
- Theta: "X is between a tight lower and upper limit" — used only when both limits match the same rate.
10.5 Limitations of Big-O Notation
Although Big-O is the most commonly used measure, it has several important limitations that a good student must understand:
It ignores constant factors. Big-O drops constants, so an O(n) algorithm that does
1000·nwork may actually be slower than an O(n²) algorithm that does2·n²work — for small or medium n. Big-O hides this difference.It describes only the worst case (upper bound). Big-O alone does not tell us about the best case or average case. For example, Quick Sort is O(n²) in the worst case but O(n log n) on average and is usually very fast in practice — Big-O by itself makes it look bad.
It is meaningful only for large n (asymptotic). Big-O describes behaviour as n → ∞. For small inputs, an algorithm with a worse Big-O can outperform one with a better Big-O. So Big-O is a guide to scalability, not to performance on tiny inputs.
It ignores lower-order terms. Two algorithms that are both O(n²) — say
n²andn² + n— are treated as identical, even though one does measurably more work.It does not capture real-world hardware factors. Cache behaviour, memory access patterns, disk I/O, and parallelism strongly affect real running time but are invisible to Big-O.
Same Big-O does not mean same speed. Two O(n log n) sorts (Merge Sort and Quick Sort) can differ greatly in real running time and memory usage even though they share the same Big-O class.
Conclusion. Big-O is an excellent first-level tool for comparing how algorithms scale, but practical algorithm selection should also consider constant factors, the average case (Θ where possible), memory usage, and the expected input size.
Important Questions with Full Answers
Short Questions (2 marks each)
Q1. What is asymptotic notation? Asymptotic notation is a mathematical way of describing the growth rate of an algorithm's running time (or space) as the input size n becomes very large (n → ∞). It ignores constant factors and lower-order terms and keeps only the dominant term, allowing hardware-independent comparison of algorithms.
Q2. Define Big-O notation. f(n) = O(g(n)) if there exist positive constants c and n₀ such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n₀. It represents the upper bound, i.e., the worst-case growth — the algorithm takes at most this much time.
Q3. Differentiate between Big-O and Omega notation. Big-O gives the upper bound (the algorithm takes at most this much time, describing the worst case), whereas Omega gives the lower bound (the algorithm takes at least this much time, describing the best case).
Q4. When is Theta notation used? Theta notation is used when the upper bound (O) and the lower bound (Ω) of an algorithm are the same function, giving a tight/exact bound: c₁·g(n) ≤ f(n) ≤ c₂·g(n) for all n ≥ n₀.
Q5. State any two limitations of Big-O notation. First, Big-O ignores constant factors and lower-order terms, so an O(n) algorithm with a huge constant can be slower than an O(n²) one for small inputs. Second, it describes only the worst case and says nothing about the best or average case.
Q6. Give the Big-O of binary search and bubble sort. Binary search is O(log n); bubble sort is O(n²) in the worst case.
Q7. Arrange these in increasing order of growth: O(n²), O(1), O(n log n), O(log n), O(n). O(1) < O(log n) < O(n) < O(n log n) < O(n²).
Q8. What does "dominant term" mean in growth analysis? The dominant term is the fastest-growing term in a running-time expression; for large n it outweighs all other terms, so the growth class is determined by it alone. For example, in 3n² + 5n + 100 the dominant term is 3n², giving O(n²).
Long Questions (6 marks each)
Q1. Explain Big-O, Omega, and Theta notations with their formal definitions and a diagram-style description.
The three asymptotic notations describe how an algorithm's running time grows with input size.
Big-O (upper bound): f(n) = O(g(n)) if there exist constants c > 0 and n₀ such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n₀. Graphically, f(n) stays below the curve c·g(n) beyond n₀. It describes the worst case.
Omega (lower bound): f(n) = Ω(g(n)) if there exist constants c > 0 and n₀ such that 0 ≤ c·g(n) ≤ f(n) for all n ≥ n₀. Graphically, f(n) stays above c·g(n) beyond n₀. It describes the best case.
Theta (tight bound): f(n) = Θ(g(n)) if there exist constants c₁, c₂ > 0 and n₀ such that c₁·g(n) ≤ f(n) ≤ c₂·g(n) for all n ≥ n₀. Graphically, f(n) is sandwiched between two multiples of g(n). Theta holds only when O and Ω are the same, giving the exact growth rate.
Q2. Prove step by step that f(n) = 2n + 3 is O(n), Ω(n), and hence Θ(n).
- O(n): We want 2n + 3 ≤ c·n. For n ≥ 3, since 3 ≤ n, we get 2n + 3 ≤ 2n + n = 3n. So c = 3, n₀ = 3 → f(n) = O(n).
- Ω(n): We want c·n ≤ 2n + 3. Take c = 2: 2n ≤ 2n + 3 is true for all n ≥ 1. So c = 2, n₀ = 1 → f(n) = Ω(n).
- Θ(n): Since f(n) is both O(n) and Ω(n), combining gives 2n ≤ 2n + 3 ≤ 3n for all n ≥ 3. With c₁ = 2, c₂ = 3, n₀ = 3, f(n) = Θ(n).
Q3. Explain the common growth functions with examples and order them, and state why lower growth is preferred for large inputs.
Common growth functions, from slowest- to fastest-growing, are O(1) (constant, e.g., array access), O(log n) (logarithmic, e.g., binary search), O(n) (linear, e.g., linear search), O(n log n) (e.g., merge sort), O(n²) (quadratic, e.g., bubble sort), and O(2ⁿ) (exponential, e.g., naïve recursive Fibonacci). As n grows large, higher-growth functions increase dramatically faster: for instance, an O(2ⁿ) algorithm becomes infeasible even for moderate n, while O(log n) and O(1) stay nearly flat. Therefore, for large inputs we prefer algorithms with lower growth classes because their running time scales far better.
Long Questions (10 marks each)
Q1. Describe all three asymptotic notations in detail with formal definitions, step-by-step examples, and their relationship. Include the summary table.
Asymptotic notation describes the growth rate of an algorithm's time/space as n → ∞, ignoring constants and lower-order terms.
Big-O (upper bound): f(n) = O(g(n)) if 0 ≤ f(n) ≤ c·g(n) for constants c > 0 and n₀, for all n ≥ n₀. Example: to show 2n + 3 = O(n), note that for n ≥ 3, 2n + 3 ≤ 2n + n = 3n, giving c = 3, n₀ = 3. Big-O describes the worst case.
Omega (lower bound): f(n) = Ω(g(n)) if 0 ≤ c·g(n) ≤ f(n) for constants c > 0 and n₀, for all n ≥ n₀. Example: to show 2n + 3 = Ω(n), take c = 2; then 2n ≤ 2n + 3 for all n ≥ 1, giving c = 2, n₀ = 1. Omega describes the best case.
Theta (tight bound): f(n) = Θ(g(n)) if c₁·g(n) ≤ f(n) ≤ c₂·g(n) for constants c₁, c₂ > 0 and n₀. Example: since 2n + 3 is both O(n) and Ω(n), we have 2n ≤ 2n + 3 ≤ 3n for n ≥ 3, giving c₁ = 2, c₂ = 3, n₀ = 3, so 2n + 3 = Θ(n).
Relationship: f(n) = Θ(g(n)) if and only if f(n) = O(g(n)) and f(n) = Ω(g(n)). Big-O bounds from above, Omega from below, and Theta holds when the two coincide, pinning the exact growth rate.
| Notation | Relation | Bound | Case |
|---|---|---|---|
| O(g(n)) | f(n) ≤ c·g(n) | Upper | Worst |
| Ω(g(n)) | f(n) ≥ c·g(n) | Lower | Best |
| Θ(g(n)) | c₁·g(n) ≤ f(n) ≤ c₂·g(n) | Tight | Exact |
Q2. What are the limitations of Big-O notation? Explain with an example why an O(n²) algorithm might outperform an O(n) algorithm.
Big-O is the most widely used measure of algorithmic complexity, but it has several limitations. (1) It ignores constant factors, so a large constant hidden inside an O(n) algorithm is invisible. (2) It describes only the worst case, ignoring best and average cases that may matter more in practice. (3) It is asymptotic, meaningful only for large n, so it says little about small inputs. (4) It ignores lower-order terms, treating n² and n² + n as the same. (5) It ignores real-world factors such as cache performance, memory access, and parallelism. (6) Two algorithms with the same Big-O can differ greatly in actual speed and memory (e.g., Merge Sort vs Quick Sort, both O(n log n)).
Example where O(n²) beats O(n): suppose algorithm A is O(n) but does 1000·n + 5000 operations, while algorithm B is O(n²) but does 2·n² operations. For n = 10, A does about 15,000 operations while B does only 200 — so B is much faster for small inputs. Only when n grows large (beyond about n = 500) does A's better growth class make it faster. This shows that Big-O predicts scalability for large inputs but can be misleading for small or medium inputs where constants dominate.
End of Unit X — Growth Functions.