✅ Asymptotic Notations

---

✅ 1. Introduction

Asymptotic Notations are mathematical tools used to describe the time complexity and space complexity of an algorithm when the input size n becomes very large.

✅ They help us to:

• Measure algorithm performance
• Compare two algorithms
• Ignore constants and less important terms
• Focus on growth rate of algorithm

📌 Example:
If an algorithm takes 5n + 10 operations, for large n, the main term is n.
So complexity becomes O(n).

---

✅ 2. Why Asymptotic Notations are Needed?

As input size increases, the execution time changes.
Asymptotic notations help us to calculate how fast the algorithm grows.

✅ Benefits:

• Independent of machine speed
• Independent of programming language
• Easy comparison of algorithms
• Useful for large data problems

---

✅ 3. Types of Asymptotic Notations

The main asymptotic notations are:

1. ✅ Big-O Notation (O) → Worst Case
2. ✅ Big-Ω Notation (Ω) → Best Case
3. ✅ Big-Θ Notation (Θ) → Average / Exact Case

(Other notations also exist like little-o and little-ω, but these 3 are most important for BCA.)

---

✅ 4. Big-O Notation (O) – Worst Case

✅ Definition

Big-O notation represents the upper bound of an algorithm.
It tells the maximum time an algorithm may take in the worst situation.

📌 Meaning:
Even in the worst case, algorithm will not take more time than O(f(n)).

✅ Example:
Linear Search in array:

• Best case: element found at first index → O(1)
• Worst case: element found at last or not found → O(n) ✅

📌 Example function:
T(n) = 3n + 5
In Big-O:
👉 O(n) (ignore constants)

✅ Common Big-O examples:

• O(1) → constant time
• O(n) → linear time
• O(n²) → quadratic time

---

✅ 5. Big-Ω Notation (Ω) – Best Case

✅ Definition

Big-Ω notation represents the lower bound of an algorithm.
It tells the minimum time required by an algorithm in the best case.

✅ Example:
Linear Search:

• Best case: element found at first position → Ω(1) ✅

📌 Example function:
T(n) = 3n + 5
In Big-Ω:
👉 Ω(n)

✅ Best case helps to know minimum time when conditions are favorable.

---

✅ 6. Big-Θ Notation (Θ) – Average / Tight Bound

✅ Definition

Big-Θ notation represents the tight bound of an algorithm.
It tells the exact or average growth rate of the algorithm.

👉 Big-Θ is used when both upper and lower bounds are the same.

✅ Example:
If algorithm always takes n steps:

• Upper bound = O(n)
• Lower bound = Ω(n)
  So,
  ✅ Tight bound = Θ(n)

📌 Example function:
T(n) = 4n + 20
Big-Θ:
👉 Θ(n)

---

✅ 7. Summary Table (Very Important for Exam)

Notation	Name	Represents	Meaning
O(f(n))	Big-O	Upper Bound	Worst case time
Ω(f(n))	Big-Omega	Lower Bound	Best case time
Θ(f(n))	Big-Theta	Tight Bound	Average / exact time

---

✅ 8. Simple Example (For Better Understanding)

✅ Example: Linear Search

Search an element in array of size n

• Best Case: element found at first position
  ✅ Time = Ω(1)
• Worst Case: element found at last / not found
  ✅ Time = O(n)
• Average Case: found somewhere in middle
  ✅ Time = Θ(n)

---

✅ 9. Important Note (How We Simplify Functions)

While calculating asymptotic complexity:

✅ Ignore:

• Constants
• Lower order terms

Example:
T(n) = 6n² + 3n + 10

For large n, the highest power dominates:
✅ Complexity = O(n²)

---

✅ Conclusion

Asymptotic notations are used to describe the performance of algorithms in terms of time and space for large input size. The most commonly used notations are Big-O (worst case), Big-Ω (best case) and Big-Θ (average or tight bound).

---