निम्नलिखित को सुमेलित कीजिए:

सूची-I	सूची-II
A. इन्सर्शन सॉर्ट	I. T(n) = 2T(n/2) + O(n)
B. हीप सॉर्ट	II. T(n) = T(n/2) + k
C. मर्ज सॉर्ट	III. T(n) = T(n − 1) + log2(n)
D. बाइनरी सर्च	IV. T(n) = T(n-1) + n

सही उत्तर A - IV, B - III, C - I, D - II है।

Key Points

• इन्सर्शन सॉर्ट का पुनरावृत्ति संबंध (T(n) = T(n-1) + O(n)) है। ऐसा इसलिए है क्योंकि सबसे खराब स्थिति में, प्रत्येक नए तत्व की तुलना पहले से सॉर्ट किए गए सभी तत्वों के साथ की जाती है, जिससे प्रत्येक तत्व के लिए O(n) इन्सर्शन समय होता है।
• हीप सॉर्ट एक हीप बनाने और बार-बार अधिकतम तत्व को हटाने पर आधारित है। इसकी समय जटिलता का विश्लेषण आम तौर पर O(n log n) समग्र रूप से किया जाता है। यह सूचीबद्ध अधिक विशिष्ट पुनरावृत्ति संबंधों में से किसी एक में सीधे फिट नहीं होता है।
• मर्ज सॉर्ट एक क्लासिक डिवाइड-एंड-कॉनकर एल्गोरिथ्म है जिसमें पुनरावृत्ति संबंध (T(n) = 2T(n/2) + O(n)) है। यह संबंध इसलिए उत्पन्न होता है क्योंकि एल्गोरिथ्म सरणी को दो हिस्सों में विभाजित करता है, प्रत्येक आधे को पुनरावर्ती रूप से सॉर्ट करता है, और फिर सॉर्ट किए गए हिस्सों को O(n) समय में मर्ज करता है।
• सॉर्टेड ऐरे पर बाइनरी सर्च का पुनरावृत्ति संबंध (T(n) = T(n/2) + k) होता है (जहाँ k एक स्थिर समय ऑपरेशन है)। ऐसा इसलिए है क्योंकि बाइनरी सर्च बार-बार सर्च अंतराल को तब तक आधा कर देता है जब तक कि लक्ष्य तत्व नहीं मिल जाता या अंतराल खाली नहीं हो जाता है।