📘 Asymptotic Notation
1️⃣ Introduction
When analyzing algorithms, exact execution time is not important because it depends on:
- Hardware
- Programming language
- Compiler
- Operating system
Instead, we study how the running time grows with input size (n).
This is done using asymptotic notation.
👉 Asymptotic notation describes the behavior of an algorithm for large input sizes, ignoring constants and lower-order terms.
2️⃣ Purpose of Asymptotic Notation
Asymptotic notation is used to:
- Measure algorithm efficiency
- Compare different algorithms
- Predict performance for large inputs
- Express time and space complexity
- Focus on growth rate, not exact time
3️⃣ Types of Asymptotic Notation
🔹 1. Big-O Notation O(f(n))
🔸 Definition
Big-O notation represents the upper bound of an algorithm’s running time.
It tells us the maximum time an algorithm will take in the worst case.
📌 Formal Definition:
An algorithm is O(f(n)) if there exist constants c > 0 and n₀ such that:
T(n) ≤ c·f(n) for all n ≥ n₀
🔸 Example
T(n) = 3n² + 5n + 10
O(n²)
🔸 Common Algorithms
- Linear Search → O(n)
- Binary Search → O(log n)
- Merge Sort → O(n log n)
🔹 2. Omega Notation Ω(f(n))
🔸 Definition
Omega notation represents the lower bound of an algorithm’s running time.
It shows the minimum time required in the best case.
📌 Formal Definition:
T(n) ≥ c·f(n) for all n ≥ n₀
🔸 Example
- Linear Search (best case) → Ω(1)
- Binary Search → Ω(1)
🔹 3. Theta Notation Θ(f(n))
🔸 Definition
Theta notation represents the tight bound of an algorithm.
It gives both upper and lower bounds, meaning the algorithm grows exactly at that rate.
📌 Formal Definition:
c₁·f(n) ≤ T(n) ≤ c₂·f(n) for all n ≥ n₀
🔸 Example
T(n) = 2n + 3
Θ(n)
4️⃣ Graphical Representation (Conceptual)
- O(f(n)) → Upper curve
- Ω(f(n)) → Lower curve
- Θ(f(n)) → Tight curve between O and Ω
(Useful to draw in exams)
5️⃣ Relationship Between Notations
| Notation | Meaning | Case |
|---|---|---|
| O(f(n)) | Upper bound | Worst case |
| Ω(f(n)) | Lower bound | Best case |
| Θ(f(n)) | Tight bound | Average / Exact |
6️⃣ Example Analysis Using Asymptotic Notation
🔹 Linear Search
| Case | Notation |
|---|---|
| Best | Ω(1) |
| Average | Θ(n) |
| Worst | O(n) |
🔹 Binary Search
| Case | Notation |
|---|---|
| Best | Ω(1) |
| Average | Θ(log n) |
| Worst | O(log n) |
7️⃣ Rules for Using Asymptotic Notation
- Ignore constant factors
- Ignore lower-order terms
- Consider dominant term
- Use Big-O for worst-case analysis
- Use Θ when exact growth is known
📌 Example:
7n³ + 3n² + 5 → O(n³)
8️⃣ Importance in Algorithm Design
- Helps choose efficient algorithms
- Prevents poor scalability
- Essential for large-scale systems
- Foundation of DAA concepts
9️⃣ Exam-Oriented Key Points
- Worst-case (Big-O) is most commonly used
- Θ gives the most accurate growth rate
- Ω is less frequently used but important
- Always mention input size (n)
🔚 Conclusion
Asymptotic notation provides a machine-independent, scalable, and theoretical way to analyze algorithm performance.
Asymptotic notation focuses on how fast an algorithm grows, not how fast it runs on a particular machine.