DAA: Asymptotic Analysis

Asymptotic Analysis is a technique used in the Design and Analysis of Algorithms (DAA) to evaluate the efficiency of an algorithm — its running time and memory usage — as the input size (n) grows toward infinity. Instead of measuring exact execution time (which depends on hardware, compiler, etc.), asymptotic analysis measures how the cost scales with input size.

Key Idea: We are interested in the rate of growth of an algorithm's cost function, not its exact value. Machine-independent analysis lets us compare algorithms fairly.

1. Why Not Just Measure Running Time?

Measuring actual wall-clock time has problems:

• Depends on the hardware (CPU speed, RAM).
• Depends on the programming language and compiler optimizations.
• Depends on the input data (already sorted vs. random).
• Cannot compare algorithms before implementing them.

Asymptotic analysis removes these dependencies by expressing cost as a function of input size n.

2. The Three Asymptotic Notations

Big-O Notation (O) — Upper Bound

Describes the worst-case growth rate. f(n) grows no faster than g(n).

O(g(n)) = { f(n) : ∃ positive constants c and n₀ such that
0 ≤ f(n) ≤ c·g(n)  for all n ≥ n₀ }

Example: 3n + 2 = O(n), because 3n + 2 ≤ 4n for all n ≥ 2 (here c = 4, n₀ = 2).

Big-Omega Notation (Ω) — Lower Bound

Describes the best-case growth rate. f(n) grows at least as fast as g(n).

Ω(g(n)) = { f(n) : ∃ positive constants c and n₀ such that
0 ≤ c·g(n) ≤ f(n)  for all n ≥ n₀ }

Example: 3n + 2 = Ω(n), because 3n + 2 ≥ 3n for all n ≥ 1 (here c = 3, n₀ = 1).

Big-Theta Notation (Θ) — Tight Bound

Describes both bounds — the algorithm grows exactly at the rate of g(n) (up to constants).

Θ(g(n)) = { f(n) : ∃ positive constants c₁, c₂, and n₀ such that
0 ≤ c₁·g(n) ≤ f(n) ≤ c₂·g(n)  for all n ≥ n₀ }

Example: 3n + 2 = Θ(n), since it is sandwiched between c₁·n and c₂·n.

Relationship: Θ(g(n)) = O(g(n)) ∩ Ω(g(n)). If an algorithm is Θ(n), it is also O(n) and Ω(n).

3. Visual Intuition

Cost │ ┌────────────── c₂·g(n) (Big-O upper bound) │ ╱───────────────────── │ ╱ f(n) ←── actual cost curve │ ╱ ┌────────────────────── c₁·g(n) (Big-Ω lower bound) │ ╱── │ ╱ │ ╱ │ ╱ ←────────── n₀ └────────────────────────────────────► Input size (n)

4. Common Growth Rates (Complexity Classes)

Notation	Name	Example Algorithm
O(1)	Constant	Array index access, hash table lookup
O(log n)	Logarithmic	Binary search
O(n)	Linear	Linear search, finding max
O(n log n)	Linearithmic	Merge sort, Heap sort, Quick sort (avg)
O(n2)	Quadratic	Bubble sort, Insertion sort, Selection sort
O(n3)	Cubic	Naive matrix multiplication
O(2n)	Exponential	Subset generation, Tower of Hanoi
O(n!)	Factorial	Brute-force Traveling Salesman, permutations

Growth order (slowest to fastest):

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

5. Growth Rate Comparison Table

n	log n	n	n log n	n2	2n
8	3	8	24	64	256
16	4	16	64	256	65,536
32	5	32	160	1,024	~4.3 × 109
1024	10	1024	10,240	~106	astronomical

Observation: For large n, the difference between O(n log n) and O(n²) becomes enormous — this is why algorithm choice matters more than micro-optimizations.

6. Solved Examples: Analyzing Loops

Example 1 — Single loop: O(n)

for (int i = 0; i < n; i++) {
    // O(1) work
    sum = sum + i;
}
// Runs n times → O(n)
    

Example 2 — Nested loops: O(n²)

for (int i = 0; i < n; i++) {          // n times
    for (int j = 0; j < n; j++) {      // n times each
        matrix[i][j] = 0;               // O(1)
    }
}
// n × n = n² → O(n²)
    

Example 3 — Halving loop: O(log n)

for (int i = n; i > 1; i = i / 2) {
    // O(1) work
}
// n, n/2, n/4, ..., 1 → log₂n iterations → O(log n)
    

Example 4 — Sequential loops: O(n) + O(n²) = O(n²)

for (i = 0; i < n; i++) { ... }         // O(n)
for (i = 0; i < n; i++)
    for (j = 0; j < n; j++) { ... }     // O(n²)

// Sum rule: O(n) + O(n²) = O(n²) — drop the lower-order term
    

7. Rules for Simplifying Complexity

Rule	Statement
Drop constants	O(5n) → O(n), O(100) → O(1)
Drop lower-order terms	O(n2 + n + 7) → O(n2)
Sum rule (sequential)	O(f(n)) + O(g(n)) → O(max(f(n), g(n)))
Product rule (nested)	O(f(n)) × O(g(n)) → O(f(n) × g(n))
Log base is irrelevant	O(log2 n) = O(log10 n) → O(log n)

8. Best, Worst, and Average Case

These describe input scenarios, while O/Ω/Θ describe bounds. They are related but distinct concepts.

Case	Definition	Example: Linear Search
Best Case	Minimum time over all inputs of size n	Element at first position → Ω(1)
Worst Case	Maximum time over all inputs of size n	Element at last / not present → O(n)
Average Case	Expected time over all inputs (probabilistic)	Element at middle on average → Θ(n)

Common exam trap: "Worst case" is not the same as "Big-O". An algorithm's worst case is usually expressed using Big-O, but Big-O is a mathematical bound that can apply to any case.

9. Properties of Asymptotic Notations

Property	Statement
Reflexivity	f(n) = O(f(n)), f(n) = Ω(f(n)), f(n) = Θ(f(n))
Transitivity	f(n) = O(g(n)) and g(n) = O(h(n)) ⟹ f(n) = O(h(n))
Symmetry	f(n) = Θ(g(n)) ⟺ g(n) = Θ(f(n))
Transpose Symmetry	f(n) = O(g(n)) ⟺ g(n) = Ω(f(n))
Sum	f(n) = O(g(n)) and h(n) = O(g(n)) ⟹ f(n) + h(n) = O(g(n))

10. Key Takeaways

• O = upper bound (≤), Ω = lower bound (≥), Θ = tight bound (=).
• Asymptotic analysis is machine-independent — it compares algorithms by growth rate, not execution time.
• Simplify by dropping constants and lower-order terms.
• Nested loops → multiply complexities; sequential blocks → take the maximum.
• For large inputs, an O(n log n) algorithm will always beat an O(n²) algorithm, regardless of constants.

11. Practice Questions

1. Prove that 5n² + 3n = O(n²) by finding constants c and n₀.
2. What is the time complexity of binary search? Justify using the recurrence T(n) = T(n/2) + 1.
3. Is 2ⁿ⁺¹ = O(2ⁿ)? Is 2²ⁿ = O(2ⁿ)? (Hint: first yes, second no.)
4. Analyze the complexity of for (i=1; i<=n; i++) for (j=1; j<=i; j++) sum++; (Answer: O(n²) — the inner loop runs 1 + 2 + ... + n = n(n+1)/2 times.)