---

📘 Lower Bound on Sorting

1️⃣ Introduction

In algorithm analysis, the lower bound of a problem represents the minimum possible time required to solve the problem, regardless of the algorithm used.

👉 For sorting, the lower bound tells us:

No comparison-based sorting algorithm can be faster than a certain limit.

---

2️⃣ Meaning of Lower Bound

• It is the best possible time complexity for solving a problem
• Represented using Ω (Omega notation)
• Helps in understanding optimality of algorithms

📌 Example:
If lower bound is Ω(n log n), then no algorithm can do better than this in worst case.

---

3️⃣ Lower Bound for Comparison-Based Sorting

🔹 Statement

Any comparison-based sorting algorithm requires at least:
[
\Omega(n \log n)
]
comparisons in the worst case.

---

4️⃣ Why Lower Bound is Ω(n log n)?

🔹 Key Idea: Decision Tree Model

• Sorting algorithms can be represented as a binary decision tree
• Each node represents a comparison
• Each leaf represents a possible sorted order

---

5️⃣ Total Possible Permutations

For n elements, number of possible orderings:
[
n!
]

👉 A sorting algorithm must distinguish between all these permutations.

---

6️⃣ Height of Decision Tree

• A binary tree with height h has at most:
  [
  2^h \text{ leaves}
  ]
• Since we need at least n! leaves:
  [
  2^h \ge n!
  ]

---

7️⃣ Taking Logarithm

[
h \ge \log_2(n!)
]

Using approximation:
[
\log(n!) \approx n \log n
]

👉 Therefore:
[
h = \Omega(n \log n)
]

---

8️⃣ Conclusion from Decision Tree

• Minimum number of comparisons = Ω(n log n)
• This is the lower bound for comparison sorting

---

9️⃣ Implications

• Algorithms like:
  • Merge Sort
  • Heap Sort
    achieve O(n log n) → optimal

✔ They match the lower bound
✔ Cannot be improved further (in comparison model)

---

🔟 Exception: Non-Comparison Sorting

🔹 Algorithms like:

• Counting Sort
• Radix Sort
• Bucket Sort

These can achieve:
[
O(n)
]

👉 Why?

• They do not rely on comparisons

---

1️⃣1️⃣ Summary Table

Type of Sorting	Lower Bound
Comparison-Based	Ω(n log n)
Non-Comparison-Based	Can be O(n)

---

1️⃣2️⃣ Importance of Lower Bound

• Helps identify optimal algorithms
• Provides theoretical limit
• Used in complexity analysis
• Guides algorithm design

---

🔚 Conclusion

The lower bound for comparison-based sorting is Ω(n log n), which means no algorithm based purely on comparisons can sort faster than this.

Merge Sort and Heap Sort are optimal because they match this lower bound.

---

📌 Exam Tip

👉 Always write:

• Decision tree concept
• n! permutations
• log(n!) ≈ n log n
• Final result: Ω(n log n)

---