____________method is often used to prove lower bounds in sorting.

Recursion tree

Master theorem

Decision tree

Dynamic programming

তথ্য ও যোগাযোগ প্রযুক্তি

তথ্য প্রযুক্তির ধারণা (Information Technology - IT)

বিসিএস

উত্তরের বিবরণ

Decision Tree Method হলো এমন একটি গুরুত্বপূর্ণ গাণিতিক কৌশল, যা comparison-based sorting algorithms–এর ক্ষেত্রে lower bound প্রমাণের জন্য ব্যবহৃত হয়। এটি অ্যালগরিদম কতগুলো তুলনা (comparison) করতে বাধ্য, তা বিশ্লেষণ করে একটি সীমা নির্ধারণ করে, যাতে বোঝা যায় কোনো sorting algorithm এর চেয়ে দ্রুততর হতে পারে না।

মূল ধারণা:
Decision tree এমন একটি বাইনারি ট্রি (binary tree) যা কোনো sorting algorithm–এর তুলনামূলক ধাপগুলোকে মডেল করে। প্রতিটি internal node দুটি উপাদানের মধ্যে একটি তুলনাকে (comparison) উপস্থাপন করে, এবং প্রতিটি leaf node ইনপুটের একটি নির্দিষ্ট permutation (বিন্যাস) নির্দেশ করে।
কাজের প্রক্রিয়া:
একটি sorting algorithm যদি n সংখ্যক উপাদানকে সাজাতে চায়, তবে সম্ভাব্য বিন্যাসের সংখ্যা হবে n! (factorial)। তাই decision tree–তে অন্তত n! সংখ্যক leaves থাকতে হবে, যাতে প্রতিটি বিন্যাসের জন্য একটি সম্ভাব্য আউটপুট পথ থাকে।
উচ্চতা (Height) বিশ্লেষণ:
কোনো বাইনারি ট্রি–এর সর্বনিম্ন উচ্চতা (h) যখন n! টি leaf থাকে, তা হয়—
[
h = \lceil \log_2 (n!) \rceil
]
অর্থাৎ, এটি নির্দেশ করে যে সবচেয়ে খারাপ পরিস্থিতিতে (worst case) অ্যালগরিদমকে অন্তত এই সংখ্যক comparison করতে হবে।
Stirling’s Approximation অনুযায়ী:
[\log_2(n!) \approx n \log_2 n - n \log_2 e]
যা Ω(n log n) এর সমান ক্রমে বৃদ্ধি পায়। এইভাবে প্রমাণিত হয় যে কোনো comparison-based sorting algorithm–এর সর্বনিম্ন গাণিতিক সীমা (lower bound) হলো Ω(n log n)।
উপসংহার:
Decision tree পদ্ধতি ব্যবহার করে দেখানো যায় যে কোনো অ্যালগরিদম, যা কেবলমাত্র তুলনার মাধ্যমে সাজায়, তা Ω(n log n)–এর কম সংখ্যক comparison ব্যবহার করে সম্পন্ন করা সম্ভব নয়। এটি Merge Sort, Heap Sort, Quick Sort প্রভৃতি অ্যালগরিদমের তাত্ত্বিক সীমা নির্ধারণের ভিত্তি হিসেবে ব্যবহৃত হয়।

অতএব, সঠিক উত্তর হলো গ) Decision Tree, কারণ এটি sorting algorithms–এর জন্য গাণিতিকভাবে প্রমাণযোগ্য সর্বনিম্ন সীমা নির্ধারণে সবচেয়ে উপযুক্ত পদ্ধতি।