Lower Bound

লোয়ার বাউন্ড

একটা problem-এর নিচের সীমা — কোনো algorithm-ই তার চেয়ে ভালো করতে পারে না; comparison sort-এর Ω(n log n) এমনই proven এক সীমা।

also: problem lower bound, omega bound

Upper bound বলে “এত ভালো করা সম্ভব”; lower bound বলে “এর চেয়ে ভালো অসম্ভব”। দুটো মিললেই problem closed — আর উন্নতির জায়গা নেই।

Comparison sort-এর proof ছোট্ট: n element-এর n!টা সম্ভাব্য order, আর প্রতিটা comparison এক binary decision —

decision tree-এর leaf ≥ n!
height ≥ log₂(n!) = Θ(n log n)

তাই mergesort/heapsort already optimal — দ্রুততর comparison sort অসম্ভব। Radix বা counting sort সীমাটা ভাঙে না, এড়িয়ে যায় — ওরা comparison-ই করে না, key-র bit সরাসরি address হিসেবে ব্যবহার করে।

Lower bound সবসময় model-এর উপর খাটে — comparison model, algebraic decision tree, cell-probe। Bound পড়ার আগের প্রশ্ন: কোন model?